Skip to main content

Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
96 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 $$ \...
Amir's user avatar
  • 544
2 votes
1 answer
107 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 ...
John's user avatar
  • 412
3 votes
1 answer
89 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 \...
badboul's user avatar
  • 77
0 votes
1 answer
174 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 ...
The T's user avatar
  • 159
0 votes
0 answers
46 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 ...
happyfeet's user avatar
12 votes
2 answers
699 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 ...
Prafullkumar Tale's user avatar
0 votes
0 answers
32 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 ...
Walid Hanafy's user avatar
1 vote
0 answers
71 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 ...
ironmanaudi's user avatar
0 votes
0 answers
17 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? ...
Tim's user avatar
  • 1
2 votes
0 answers
26 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 ...
John's user avatar
  • 412
0 votes
0 answers
71 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 ...
rivana's user avatar
  • 65
3 votes
0 answers
130 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 ...
Andrija Sevaljevic's user avatar
6 votes
2 answers
634 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 ...
EGME's user avatar
  • 161
2 votes
0 answers
102 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$ ...
sally's user avatar
  • 21
2 votes
0 answers
102 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 ...
Denis's user avatar
  • 8,903
3 votes
1 answer
192 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 ...
Ctenochaetus's user avatar
8 votes
1 answer
245 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 ...
user avatar
1 vote
2 answers
177 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 ...
Qalat's user avatar
  • 11
0 votes
1 answer
86 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, ...
vinaych's user avatar
  • 11
7 votes
1 answer
188 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 ...
B A's user avatar
  • 98
2 votes
0 answers
116 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 ...
ddr's user avatar
  • 21
-1 votes
1 answer
166 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 ...
user1868607's user avatar
  • 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$ ...
Alexey Milovanov's user avatar
6 votes
1 answer
268 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. ...
Alexey Milovanov's user avatar
1 vote
1 answer
210 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 ...
NayCey's user avatar
  • 11
1 vote
0 answers
136 views

Can NP-complete language be in $mP/poly$?

Can NP-complete language be in monotone $P/poly$?
qwerty43's user avatar
  • 111
0 votes
1 answer
92 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 $...
Dominic van der Zypen's user avatar
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 ...
GMB's user avatar
  • 2,403
2 votes
1 answer
162 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 ...
Russell Easterly's user avatar
0 votes
0 answers
59 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 ...
Noble Mushtak's user avatar
3 votes
0 answers
280 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$, ...
Turbo's user avatar
  • 13k
2 votes
1 answer
161 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 ...
Linda Cai's user avatar
5 votes
1 answer
298 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 $...
Punga's user avatar
  • 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 ...
luciano's user avatar
  • 61
1 vote
1 answer
288 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 ...
ColorTilesUser's user avatar
8 votes
1 answer
316 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 ...
user1868607's user avatar
  • 1,049
0 votes
1 answer
223 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 ...
user63167's user avatar
16 votes
0 answers
452 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....
M.Monet's user avatar
  • 1,429
5 votes
1 answer
664 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 ...
Abuzer Yakaryilmaz's user avatar
9 votes
0 answers
153 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. ...
William Gasarch's user avatar
1 vote
1 answer
90 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 ...
vervenumen's user avatar
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 ...
Stephane Bersier's user avatar
-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.
oompa's user avatar
  • 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$ ...
exfret's user avatar
  • 653
2 votes
1 answer
134 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}...
Manuel Dubinsky's user avatar
3 votes
2 answers
816 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 ...
Saeed's user avatar
  • 3,440
11 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 ...
StefanH's user avatar
  • 2,077
1 vote
0 answers
58 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 ...
Andras Farago's user avatar
0 votes
0 answers
276 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 ...
Iago Carvalho's user avatar
2 votes
1 answer
74 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$-...
Andras Farago's user avatar