The np-complete tag has no wiki summary.
2
votes
3answers
416 views
How can you prove that a problem is not solvable in a certain time complexity?
One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable ...
32
votes
1answer
432 views
NP-Completeness of the decision problem for the generalized 15-puzzle
I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block).
Now the ...
2
votes
1answer
222 views
in SAT resolution proofs, are all DAGs possible? [closed]
these are some probably very hard but possibly significant and deep questions related to an unusual but intriguing possible "recursive" construction/formulation in SAT, with some important "structure" ...
