Problem 1)

so make an outside function that correlates between a and a compliment. so it kinda connects the two in a way, and what this functon should do is if u have an input within A, it should be be able to map out a value not in A when you apply the function

<=m is a transitive relation

A transitive relation is defined as a relation for if all elements a, b, c in X, whenever a is related to b and b is related to c, then a is also related to c.

In this language, A is reducible to B only if there is a function that takes all elements in A and returns elements in B.

if they are compliments, you know when to halt in both cases so you can decide whether or not it is in the language

Problem 2)

reduce etm into disjoint
intesrsection of two languages that dont accept anything


Problem 3) Algorithm to decide triangle:


On any input:

For every combination of 3 vertices in the input (for example, A, B, C), return true if G contains all edges that create a cycle (AB, BC, CA). If the entire input is exhausted and the algorithm has not returned true, return false.

This algorithm runs in polynomial time. This is because there are v^3 amount of vertices (V = # of vertices), and so the runtime for enumerating each vertex is O(n^3). To verify that there exists the 3 edges (AB, BC, CA), it takes O(E) time where E is the number of edges. Because the algorithm runs in O(EV^3), it runs in polynomial time. Because it runs in polynomial time, it exists in P.

Problem 4)

x1 can be true or false. so the way id go about it is ask them what happens if x1 is set to true or false. ask them if x1 is set to true or false and ask whether its satisfiable. if i ask the genie, im gonna give you x1 = True, and he tells me its true, i have to do something in response to that. n queries.