Questions tagged [np-complete]
The np-complete tag has no usage guidance.
160
questions
35
votes
1
answer
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 ...
- 607
25
votes
2
answers
1k
views
Is there an NP-complete language that contains precisely half of the n-bit instances?
Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$
$$|L\cap \{0,1\}^n|=2^{n-1}$$
holds? In other words, $L$ contains precisely half of all $n$-...
- 10.8k
24
votes
7
answers
3k
views
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
László Babai recently proved that
the Graph Isomorphism problem is in quasipolynomial time.
See also his
talk at University of Chicago,
note from the talks by Jeremy Kun
GLL post 1,
GLL post 2,
GLL ...
user17918
24
votes
3
answers
1k
views
NP complete graph problems about structural properties
(This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some ...
- 431
23
votes
3
answers
1k
views
How much would a SAT oracle help speeding up polynomial time algorithms?
Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ ...
- 10.8k
21
votes
1
answer
851
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$...
- 10.8k
19
votes
3
answers
1k
views
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
I was recently reading a very nice paper by Valiant and Vazirani which shows that if $\mathbf{NP \neq RP}$, then there can not be an efficient algorithm to solve SAT even under the promise that it is ...
- 419
19
votes
1
answer
537
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 ...
- 10.8k
18
votes
2
answers
2k
views
Are there any heuristic-free NP complete problems?
Are there any NP complete problems with no infinite subset of instances $\Phi$ such that membership in $\Phi$ can be decided in polynomial time, and for all $x \in \Phi$, $x$ can be solved in ...
- 1,082
16
votes
1
answer
1k
views
Password hashing using NP complete problems
Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
- 779
16
votes
0
answers
396
views
Is this problem on unambiguous finite automata NP-complete?
An unambiguous finite automaton (UFA) is a nondeterministic finite automaton (NFA) such
that each word has at most one accepting path. In this post, for $n\in \mathbb{N}$, what I call an $n$-UFA (resp....
- 1,217
15
votes
2
answers
419
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 ...
- 405
14
votes
2
answers
566
views
Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices
What is the complexity of the following problem?
Input:
$H$ a Hamiltonian path in $K_n$
$R \subseteq [n]^2$ a subset of pairs of vertices
a positive integer $k$
Query: is there a matching $M$ such ...
- 141
12
votes
1
answer
422
views
Which complexity class does this number theory problem belong to?
'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete.
Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
user34945
12
votes
1
answer
284
views
Slowest many-one reduction?
When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. ...
- 10.8k
12
votes
0
answers
500
views
Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?
Question
I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete.
Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$.
Where $\...
- 229
11
votes
1
answer
211
views
Natural candidates for NP-E and E-NP
It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
- 10.8k
11
votes
0
answers
384
views
Error in paper "Some NP-complete geometric problems"?
The paper in question:
M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .
This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
- 275
10
votes
4
answers
3k
views
Does Memcomputing really solve an NP-complete problem?
I came across an article published in Science "Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states", which makes some pretty astonishing claims.
...
- 301
10
votes
1
answer
753
views
Relationship between two graph optimization problems
Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph:
P1. Find a largest induced subgraph of the ...
- 10.8k
10
votes
2
answers
415
views
"Relatives" of the shortest path problem
Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
- 10.8k
10
votes
1
answer
625
views
Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic
Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1].
I am interested in a more fine-grained ...
user17918
9
votes
2
answers
508
views
NP-Complete Static Square Puzzles
In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...
9
votes
0
answers
142
views
Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?
Planar graphs are 4-colorable.
Determining if a planar graph is 3-colorable is NP-Complete.
A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable.
...
9
votes
0
answers
348
views
What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?
The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published ...
- 10.8k
8
votes
7
answers
1k
views
NP-complete decision problems on deterministic automata
Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
- 1,977
8
votes
1
answer
212
views
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
- 153
8
votes
2
answers
1k
views
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass 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 ...
- 463
8
votes
1
answer
317
views
NP-hardness on Cayley graphs
What is known about complexity of NP-hard problems on Cayley graphs?
Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
- 1,897
8
votes
1
answer
281
views
What do we know about checking real-stability of multivariate complex polynomials?
Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root ...
- 644
8
votes
1
answer
323
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, ...
- 10.8k
8
votes
0
answers
120
views
Does NP Completeness always fall on one side or the other of an intermediate computation?
Let $L$ be an NP complete language. My loose intuition for completeness suggests that, at any point in a computation tableau for $L$, either the computation has "already done an NP complete ...
- 2,333
8
votes
0
answers
155
views
Practical interactive proof schemes for NP-hard problems
Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ...
- 1,122
8
votes
0
answers
184
views
Complexity question from mathematical music theory
Fix an positive integer $N$.
A row means any linear ordering $R=(n_i)_{0\leq i <N}$ of the additive group ${\Bbb Z}/N{\Bbb Z}$.
Call $R$ a (generalized) all-interval row if the elements of the ...
- 189
7
votes
1
answer
322
views
Problem of graph bi-partition (related to graph isomorphism)
I am considering the following problem:
Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$
Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, ...
- 251
7
votes
1
answer
163
views
Complexity of Maximizing Hamming Distances Below a Threshold
Problem Statement
Is the following problem NP-Complete?
Input: A collection $S$ of binary strings, with each string of length $m$.
Goal: Compute a binary string $s^*$ of length $m$ that mazimizes the ...
- 98
7
votes
1
answer
297
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 ...
- 405
7
votes
1
answer
303
views
Cook inspiration for NP completeness
An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for ...
- 889
7
votes
0
answers
60
views
Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times
When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:
Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
- 71
7
votes
0
answers
478
views
On the shortest vector problem (is it $NP$-complete?)
Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.
Has this been derandomized?
- 12.6k
7
votes
0
answers
207
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 ...
- 11.1k
6
votes
1
answer
967
views
Does the Cook-Levin theorem relativize?
My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes. If you have a proof that the ...
user1338
6
votes
1
answer
199
views
Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis
The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ ...
- 1,081
6
votes
1
answer
395
views
Complexity of finding the largest induced subgraph with all even degrees
What is the complexity of the following problem?
Instance: Simple, undirected graph $G$, and a positive integer $k$.
Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
- 10.8k
6
votes
1
answer
143
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} ...
- 439
6
votes
1
answer
230
views
Finding a minimal addition chain for a given number
An addition chain for computing a positive integer $n$ is a sequence of natural numbers starting with $1$ and ending with $n$, such that each number in the sequence is the sum of two previous numbers.
...
- 1,859
6
votes
0
answers
137
views
Computing Sequences with Addition Chains In pseudopolynomial time?
Computing Sequence $a_1, \ldots, a_n$ with addition chains (CSAC) is the problem of finding the shortest sequence $b_1, \ldots, b_m$ with the following properties:
$b_1=1$.
Every $b_i$ with $i>1$ ...
- 1,859
5
votes
1
answer
2k
views
Magic constant to solve NP-complete problem in polynomial time
Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
- 159
5
votes
1
answer
567
views
Unary language examples between L and NP
I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $ L \subseteq NL \subseteq P = AL \subseteq NP $.
What I found after some search(e.g., Complexity zoo for unary ...
- 3,677
5
votes
1
answer
183
views
Does p-isomorphism preserve phase transition?
Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other ...
- 10.8k