-1
votes
1answer
47 views

NP vs CO vs P Problem

if we assume set of all tautology in predicate logic, with above assumption is : 1) NP Complete? 2) NP but not NP- Complete? 3) CO-NP Complete? 4? CO-NP but not CO-NP Complete? i ran into a ...
1
vote
1answer
25 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
0
votes
1answer
62 views

Algorithm for valid 3 coloring.

If we have P=NP, how can I show that a polynomial algorithm exists that given any 3 colourable graph produces a valid 3 colouring (no two adjacent vertices share the same colour)?
-4
votes
1answer
195 views

How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
1
vote
2answers
207 views

Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example: The language of Boolean expressions is Turing complete; Does this imply that ...