Questions tagged [np-complete]
The np-complete tag has no usage guidance.
176
questions
0
votes
0
answers
21
views
On the $\mathsf{NP}$ hard variant of integer factorization
In this post on whether a variant of integer factorization
$$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ integer}\mbox{ } m \in \{a, \ldots, ...
- 13.1k
5
votes
1
answer
66
views
Equal appearance of positive and negative literals in 1-IN-3SAT per variable: Is it NP-complete?
The variant is the regular 1-in-3SAT problem with only the formulae where each variable and its negation appear the same number of times in the formula.
For example, $(a\vee b\vee\neg a)\wedge(\neg a\...
- 53
1
vote
0
answers
36
views
Clause Density for guaranteed Easy (2, 3) SAT Cases
It is known that its NP-Complete to decide the satisfiability of 3-SAT instances in which every variable occurs four times.
Now given a (2, 3)-SAT instance where each clause has length 2 or 3. ...
- 831
1
vote
0
answers
163
views
Is finding the best permutation an NP-Complete problem?
We have a matrix $M$ of size $n$ by $n$ where
$M[i][j] \ge 0$ and $M[i][i] = 0$.
We want to create a permutation of integers $[1,\dots,N]$, like $\langle P_1, P_2,\dots,P_n \rangle$, such that
$$
\...
- 544
2
votes
1
answer
113
views
Constrained Bipartite Matching
Let $G = (X,Y,E)$ be a bipartite graph. For some $A \subseteq X$ we say that $A$ can be perfectly matched if there is a matching $M \subseteq E$ such that all vertices in $A$ are matched; that is, for ...
- 412
3
votes
1
answer
101
views
Deciding if max-cut with negative edge weights has a solution with positive value
I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value:
Given a graph $G=(V, E)$ and edge weights $w: E \...
- 122
0
votes
1
answer
179
views
This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?
Suppose, I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if ...
- 159
0
votes
0
answers
49
views
Unbounded Knapsack: Does Increasing capacity increase optimal value?
Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
12
votes
2
answers
711
views
Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees
Do we know any problem that satisfies the following criteria?
It is polynomial-time solvable on trees.
It is NP-complete when restricted to graphs of treewidth 2.
The problem can be encoded only ...
0
votes
0
answers
37
views
Compute a feasible schedule for scheduling on identical parallel machines?
I am considering the offline version of identical parallel machine scheduling with arrival time and deadlines while allowing preemption and no assumption regarding the agreeability of the arrival and ...
- 101
1
vote
0
answers
74
views
Hardness for find the clause for statisfiable 3-SAT problems
The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as ...
- 111
0
votes
0
answers
19
views
Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?
Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
- 1
2
votes
0
answers
32
views
Hardness of 3-Partition with Small Target Value
In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
- 412
0
votes
0
answers
76
views
The hardness of active learning with fixed budget
I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular ...
- 65
3
votes
0
answers
145
views
I am looking for a detailed list of known reductions of NP-Complete problems
I am looking for a detailed list of known reductions of NP-Complete problems. Much like Richard Karp's list of 21 NP-Complete problems has more than a dozen reductions, I am looking for a bigger ...
6
votes
2
answers
643
views
NP-complete problems where the inputs are prime numbers
Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are ...
- 161
2
votes
0
answers
104
views
Two disjoint paths with minimum product of weights -NP-completeness
I want to know whether the following problem is NP-complete;
Given an undirected graph $G=(V,E)$ with weights on each edge $e\in E$, and two vertices $s,t\in V$, find two disjoint paths $P_1, P_2$ ...
- 21
2
votes
0
answers
108
views
What kind of solver should I use for this hypergraph problem?
I have to list the solutions to the following hypergraph problem:
There is a set of nodes, linked by edges that are 2-to-1 and bidirectional. The possible directions are either direct: 2 sources and 1 ...
- 8,923
3
votes
1
answer
216
views
NP-complete problems on posets?
I'm in the midst of some doctoral research and trying to figure out a particularly tricky reduction. I think my best shot is to reduce from an NP-complete problem on posets, if one exists.
I did some ...
- 33
8
votes
1
answer
251
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 ...
user67795
1
vote
2
answers
184
views
Is this subsequence problem NP-hard?
Here is yet another "is X NP-hard?" question.
The input of the problem is the following:
A sequence of $n$ non-negative real numbers $\alpha_1, \ldots, \alpha_n$. Here $n$ is a positive ...
- 11
0
votes
1
answer
87
views
Regarding UNSAT bechmark of SATLIB found as SAT instance
I found the Satisfiable assignment to one of the UNSAT [SATLIB benchmark][1] instance, specifically uuf50-01.cnf as below answer:
[1, 2, 3, 4, -5, -6, -7, -8, 9, 10, -11, 12, 13, 14, -15, -16, 17, 18, ...
- 11
7
votes
1
answer
195
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
2
votes
0
answers
117
views
Question about #P-completeness and NP-completeness
In the book Nature of Computation by Moore & Mertens there is an exercise saying "show that if a counting problem #A is #P-complete with respect to parsimonious reductions, that is if every ...
- 21
-1
votes
1
answer
171
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 ...
- 1,049
6
votes
0
answers
141
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$ ...
- 2,013
6
votes
1
answer
275
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.
...
- 2,013
1
vote
1
answer
227
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
136
views
0
votes
1
answer
93
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
121
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,481
2
votes
1
answer
163
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 ...
- 639
0
votes
0
answers
60
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
292
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$, ...
- 13.1k
2
votes
1
answer
166
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 ...
- 51
5
votes
1
answer
301
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
57
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
301
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 ...
8
votes
1
answer
317
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 ...
- 1,049
0
votes
1
answer
232
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 ...
- 11
16
votes
0
answers
456
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,431
5
votes
1
answer
673
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,707
9
votes
0
answers
155
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
91
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
79
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 ...
- 221
-4
votes
1
answer
34
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
42
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$ ...
- 653
2
votes
1
answer
135
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
848
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,440
10
votes
9
answers
2k
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 ...
- 2,057