New answers tagged decision-problem
4
votes
Accepted
Why is 3-co-SAT not in P?
co-SAT is not asking whether there exists an unsatisfying assignment, it is asking if every assignment evaluates to false.
- 14.3k
Top 50 recent answers are included
Related Tags
decision-problem × 508complexity-theory × 168
np-complete × 133
np × 83
turing-machines × 69
computability × 66
algorithms × 64
reductions × 63
np-hard × 59
undecidability × 55
optimization × 25
time-complexity × 23
graphs × 22
satisfiability × 21
polynomial-time × 18
formal-languages × 17
regular-languages × 14
complexity-classes × 14
p-vs-np × 14
semi-decidability × 14
search-problem × 14
context-free × 13
halting-problem × 13
finite-automata × 12
terminology × 12