Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-complete]

The tag has no usage guidance.

18
votes
1answer
422 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 ...
8
votes
1answer
293 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, ...
2
votes
1answer
750 views

Multiple subset sum where subsets have complementary cardinality

$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem: Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$. Output: $k$ $\mbox{ }\...
4
votes
0answers
130 views

Symmetry of optimal solutions to discrete optimization problems

Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than ...
4
votes
1answer
301 views

Are there any implementations for zero-knowledge proofs of NP-complete problems?

It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search engine,...
1
vote
0answers
596 views

Are there upper bounds on the worst case complexity of NP-complete problems?

I have proven some problem to be (weakly) NP-complete and try to find out some algorithm to solve it exactly. Except for some pseudo-polynomial stuff, I would be happy with an algorithm running in $O(...
6
votes
0answers
178 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 ...
2
votes
1answer
287 views

Complexity of a linear algebra problem

Let matrix $M \in \{0,1\}^{r \times s}$ ($s>r$), let function $f:\Bbb Z^{} \rightarrow \pm1$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given. Is it NP-complete to decide if $\exists u \in \{0,1\}^...
-2
votes
2answers
585 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?
3
votes
2answers
442 views

Finding the identity with permutation chains

I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$. How hard is to find a sequence $...
6
votes
1answer
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} ...
3
votes
3answers
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 ...
35
votes
1answer
994 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 ...
1
vote
1answer
303 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" ...