# Questions tagged [np-complete]

The tag has no usage guidance.

114 questions
Filter by
Sorted by
Tagged with
446 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 ...
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, ...
782 views

190 views

### Generalization of SAT, where we replace OR with another symmetric function

Let $\sigma(y_1,\dots,y_k)$ denote some boolean symmetric function on $k$ boolean inputs, $\sigma:\{0,1\}^k\to\{0,1\}$. In $k$-SAT, an instance is a conjunction of clauses, where each clause is the ...
294 views

138 views

### What's complexity of this set problem which looks like “Linear Programming”?

I came up with a problem below, which looks like a linear programming problem: Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :  \forall i=1, 2, 3,...,n\space\space \left | S_{i} ...
2k 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 ...