Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
18
votes
1answer
440 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
14
votes
2answers
353 views

Poly time superset of NP complete language with infinitely many strings excluded from it

For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite? A trivial version which does not stipulate the superset to have infinite ...
1
vote
1answer
309 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" ...
35
votes
1answer
1k 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 ...
20
votes
1answer
687 views

“Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an $A\in$ P, such that $L\Delta A$...
7
votes
1answer
272 views

Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

A set is $\mathsf{P}$-immune iff it has no non-trivial $\mathsf{P}$ subset. Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to an $\mathsf{P}$-immune $\mathsf{coNP}$-complete ...
6
votes
2answers
776 views

Isn't it trivial to represent any classical physics problem in a Spin-Glass language which is NP-Complete?

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ...
8
votes
1answer
297 views

Can a natural graph problem be universally hard?

Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to any polynomial-time recognizable graph class? To avoid degenerated cases, ...
1
vote
1answer
150 views

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs. If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ...
-2
votes
2answers
597 views

Where are NP-complete problems if P=NP [closed]

Where are exactly NP-complete problems if P=NP? They will be definitely in P, but will they be P-complete?
5
votes
1answer
670 views

Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

It is known that Exact Set Cover is an NP-hard problem (Reduction from 3-SAT and 3-Coloring). Also, my minor analysis one can realize that this problem is also ETH-hard, i.e. this cannot be solved in ...
3
votes
1answer
523 views

Easier and Harder instances of NP-complete problems?

Following previous questions here and here around $NP$-complete problems (and P vs NP). Are there "easier" or "harder" (sets of) instances of an $NP$-complete problem? If yes (which i assume), how a ...
0
votes
1answer
159 views

Any result connecting an NP-complete problem with slight super-polynomial time?

Helo everybody, is there any result or research that connects some $NP$-complete problem with only slightly super-polynomial (strongly sub-exponential) time? This would not necessarily involve ...