Hot answers tagged


As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).


You are confusing NP and NP-hard in a couple places. For example, let $A$ be the problem of deciding ATL*, which is 2EXPTIME-complete. $A$ is NP-hard and polynomial-time many-one reduces to its complement, but is neither in NP nor in co-NP by the time hierarchy theorem. Recall that an NP-complete problem is one that is in NP and is NP-hard. For every NP-...


Your understanding is correct, but the takeaway here is that assuming the contradictions implies that anything can be true. Perhaps reading up on some logic rules might help, the important rule here is that $\bot$ (false) implies everything. Here is a little proof of the problem just for fun: We know that both 3-SAT and Set Cover are NP-Complete problems. ...

Only top voted, non community-wiki answers of a minimum length are eligible