Questions tagged [np-complete]
The np-complete tag has no usage guidance.
154
questions
0
votes
0
answers
118
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal polygons. Rapport showed that it is NP-complete to to decide the existence of orthogonal simple polygon that passes ...
- 20.6k
-1
votes
1
answer
126
views
Cook's theorem and universal machine
From Papadimitriou and Yannakakis, "A Note on Succinct Representations of Graphs" second parragraph of the proof of the main result.
Cook (1971) presented in his classical paper a ...
- 767
6
votes
0
answers
133
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,695
6
votes
1
answer
223
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,695
1
vote
1
answer
81
views
Exact Cover by 3-Sets variation: Partition Into Exact Covers by 3-Sets
In the Exact Cover by 3-Sets problem, we are given a set $X = \{x_1, x_2,\ldots, x_{3n}\}$ and a family of subsets $F = \{\{x_{i_1}, x_{i_2}, x_{i_3}\}\}$ of 3-element subsets of $X$.
The question is ...
- 11
1
vote
0
answers
127
views
0
votes
1
answer
84
views
Is "choosability of subsets" NP-hard?
Let $n\in\mathbb{N}$ be a positive integer, and let ${\cal A}$ be a collection of subsets of $n=\{0,\ldots,n-1\}$. We say ${\cal A}$ has the choosability property if there is $R\subseteq n$ such that $...
8
votes
0
answers
119
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,313
0
votes
0
answers
64
views
Short UNSAT Certificates for X3SAT
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
- 499
0
votes
0
answers
48
views
Relativized Version of NP^A-complete
I was reading this post about whether Cook-Levin relativizes and at the bottom of the answer, they include a quote from Computational Complexity by C. Papadimitriou (this is a longer version of the ...
- 101
3
votes
0
answers
235
views
Is the following equitable factoring problem $NP$-hard or in $P$?
Consider the following factoring problem:
Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p_i,e_i\}_{i=1}^n$, ...
- 12.5k
2
votes
1
answer
147
views
Is the weighted sum of subset prefix product problem NP-hard?
I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f: M \rightarrow R^+$ mapping each number in M to another positive number. We want to know ...
- 43
5
votes
1
answer
277
views
Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?
I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$
$\begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size $...
- 153
1
vote
0
answers
55
views
Partition of multisets of polynomials
Problem: Given a multiset S of irreducible polynomials in Z[x], say YES if S can be partitioned into two nonempty multisets A and B such that both the product of all the elements of A and the product ...
- 61
1
vote
1
answer
185
views
How to show that Color Tiles is NP-Complete
Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You ...
0
votes
0
answers
37
views
Bounded-Frequency Minimum Set Cover Problem
Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets.
Can this problem be solved in polynomial time?
Is there a nontrivial upper ...
- 101
7
votes
1
answer
299
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 ...
- 767
0
votes
1
answer
191
views
Lexicographic Boolean satisfiability
Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or ...
14
votes
0
answers
300
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,197
5
votes
1
answer
498
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,647
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.
...
1
vote
1
answer
89
views
Choosing one number from each set so that the sum of squares of each distinct number counts is minimized
Problem is as follows:
We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times ...
- 113
1
vote
2
answers
75
views
Disjoint subsets problem complexity
Is the decision problem below NP-complete?
Given sets $S_1, ... , S_n$, as well as bounds $b_1, ... , b_n$, is it possible to pick pairwise disjoint subsets $U_1, ... , U_n$ such that $U_i \subset ...
- 211
-4
votes
1
answer
31
views
Polynomial-time reducibility of Primality and 3-SAT
Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.
Thank you.
- 101
1
vote
0
answers
40
views
Efficient algorithm for finding segregators in a directed acyclic graph
Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
- 633
2
votes
1
answer
120
views
NP-completeness: sum of "some" paths in a spanning tree
I suspect this problem is NP-complete but I couldn't prove it, if anyone can help I'll be very grateful:
Instance: undirected, unweighted, connected graph $G=(V,E)$, positive integer $K \in \mathbb{Z}...
3
votes
2
answers
521
views
Is the maximum independent set in cubic planar graphs NP-complete?
In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
- 3,430
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,947
1
vote
0
answers
47
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 ...
- 10.8k
0
votes
0
answers
163
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 ...
- 185
2
votes
1
answer
67
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$-...
- 10.8k
5
votes
0
answers
106
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 $...
- 22.3k
6
votes
1
answer
377
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
10
votes
1
answer
751
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
-4
votes
1
answer
125
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 ...
- 95
1
vote
1
answer
1k
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 ...
- 121
4
votes
0
answers
75
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 ...
- 22.3k
10
votes
2
answers
357
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
5
votes
0
answers
63
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\mathbb ...
- 101
2
votes
0
answers
72
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,...
- 101
5
votes
1
answer
113
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, ...
- 1,429
11
votes
1
answer
205
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
0
votes
2
answers
243
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 ...
- 1,623
3
votes
0
answers
255
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 ...
- 47
1
vote
1
answer
264
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
1
answer
178
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" ...
- 131
2
votes
1
answer
170
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,429
0
votes
1
answer
283
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 ...
- 271
4
votes
1
answer
199
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 ...
- 71
9
votes
2
answers
494
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 ...
