Questions tagged [np-complete]
The np-complete tag has no usage guidance.
124
questions
7
votes
5answers
333 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
vote
0answers
29 views
Minimum rank graph cut
Consider the following problem:
Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle.
Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the ...
0
votes
0answers
56 views
Complexity of multi-objective optimization problems
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
2
votes
1answer
49 views
Maximum subgraph problem with unknown complexity
Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-...
4
votes
0answers
94 views
Reconstructing a colored grid with vertical and horizontal shifts
Consider the following simple problem (puzzle): given
a $N \times N$ $c$-colored grid $G$
a $N \times N$ $c$-colored target grid $G_T$
a number $m$ represented in unary
Can we transform $G$ into $...
6
votes
1answer
199 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
votes
1answer
700 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 ...
-4
votes
1answer
106 views
Example of decidable NP-hard problem that is not NP-complete [closed]
I am looking for an example of a decision problem which fulfills the following conditions:
1. It is decidable
2. It is NP-hard
3. It is not NP-complete
All my search attempts yielded examples that ...
1
vote
1answer
225 views
What languages can be reduced to a NP-complete problem in polynomial time
NP-complete: Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in ...
4
votes
0answers
66 views
Short $\exists$SO sentences over strings that define an NP-complete problem
[Q1] I'm wondering if there are some "official" SHORT existential second order sentences with ONE binary relation, over strings (over a small alphabet) that define an NP-complete set.
(Something ...
10
votes
2answers
194 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 ...
5
votes
0answers
55 views
Hardness result or reference for optimal Gaussian elimination process
I'm wondering if the following problem is NP-Complete or has any hardness result.
References on related problem are also welcome.
Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\...
2
votes
0answers
63 views
Hardness result or reference for a set partition problem
I'm wondering if the following problem is (or has been proven to be) NP-Complete.
Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.
Accept iff: there exists $\{a_i,...
5
votes
1answer
108 views
$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree?
Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$.
Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, ...
10
votes
1answer
170 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}$...
0
votes
2answers
215 views
NP-hard problems on the class of caterpillars
My question is whether there exist an NP-hard problem that has only a caterpillar as input.
By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or ...
3
votes
0answers
244 views
new subset sum approach results
I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is ...
1
vote
1answer
159 views
Does BQP contain any NP-Complete problem?
From the Wikipedia documentation, "the suspected relationship of BQP to other problem spaces" diagram suggests no intersection between NP-complete problems and BQP.
Has this been demonstrated or not?
0
votes
1answer
146 views
Subset Sum Problem and hard looking instances that are not really hard
I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
1
vote
1answer
154 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 ...
1
vote
1answer
142 views
A dominate vector subset sum problem
Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$.
Consider the ...
4
votes
1answer
89 views
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
7
votes
2answers
393 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 ...
7
votes
0answers
56 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,...
3
votes
1answer
98 views
NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?
It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049
For a problem I'm ...
11
votes
0answers
350 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 ...
16
votes
1answer
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 ...
0
votes
1answer
115 views
Is Prime Bounded Quadratic Congruence NP-complete?
Bounded Quadratic Congruence:
Instance: Three positive integers $a$, $b$ and $c$.
Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?
Bounded Quadratic ...
-1
votes
1answer
53 views
NP-Complete graph problems where a special vertex is given as input?
I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...
12
votes
0answers
443 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 $\...
1
vote
1answer
122 views
Can MONOTONE WSAT be in solved in polynomial time?
In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the ...
8
votes
0answers
138 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
vote
0answers
117 views
Generalized path cover problem in DAG
Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
1
vote
0answers
149 views
Are there any NP-complete for continuous mathematics? [closed]
Looking at this wiki page, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete ...
7
votes
2answers
860 views
Isn't it trivial to represent/reduce any classical physics problem in/to 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 ...
0
votes
1answer
50 views
Maximize graph with k cut edge operations
I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 ...
5
votes
2answers
178 views
Minimising the root-set of a spanning hyperforest of a hypergraph
I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
4
votes
1answer
176 views
Verifying that a reduction is correct
Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on ...
3
votes
2answers
174 views
Reduction of graph chromatic number to hypergraph 2-colorability
I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
3
votes
1answer
178 views
Matrix Coloring under Vertical and Horizontal Constraints
I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations.
The input consists of
A set of ...
0
votes
1answer
131 views
On polytope lattice points
Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$.
Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
4
votes
0answers
169 views
Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
Actually I found that the set of context-sensitive Languages,
$\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular ...
1
vote
0answers
72 views
Prove that finding set of $k$ vertices $S$, such that $G{\setminus}S$ is claw-free is NP-Complete
The claw in a graph $G(V,E)$ consists of a vertex $v\in V$, and it's three neighbours - $\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if $\{x_1,x_2,x_3\}$ form an independent set in $G$.
The problem asks us ...
1
vote
1answer
189 views
Fixed parameter tractable Integer Programming and $FPP$
Integer programming is $NP$ complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of $P$-complete or in parametrized analogue of $...
3
votes
1answer
260 views
Is deciding whether all satisfying assignments are NAE assignments coNP-complete?
Let the language $L$ consist of the $k$-CNF formulas $\phi$ with the property that any satisfying assignment $x$ of $\phi$ is a Not-All-Equal (NAE) assignment, i.e. every clause of $\phi$ has at least ...
0
votes
1answer
351 views
A proof that Partition into forests is NP-Complete
The partition a graph into forests problem is defined as:
Given a Graph $G=(V,A)$, and a positive integer $K \le |V|$, can the vertices $V$ be partitioned into disjoint sets $V_1$, ..., $V_k$, $k \le ...
1
vote
1answer
142 views
Unambiguous SAT and sparse languages
What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
3
votes
2answers
557 views
A generalization of edge cover
Suppose we are given a general (connected) undirected graph $G = (V, E)$. An EDGE COVER asks a set $S\subseteq E$ of the minimum number of edges, such that each vertex $v\in V$ is incident to at least ...
14
votes
2answers
548 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 ...
4
votes
1answer
254 views
UnambiguousSAT reductions
Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.
Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but ...
