Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

Filter by
Sorted by
Tagged with
0
votes
1answer
95 views

Reduce Subset-Sum to Sat

Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers. SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn }...
0
votes
0answers
110 views

Prove that the following problem is NP-complete

I am studying computational complexity and trying to prove that the following problem is NP-complete. Ursula is planning to make all the city’s kids sick the day before Thanksgiving, by overfeeding ...
0
votes
1answer
21 views

Reduce subset sum to simple path

I have a similar question as this post:Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost My question: Given a weighted and directed graph $G$, it ...
0
votes
0answers
24 views

Is Knapsack-optimization problem NP-hard while Knapsack-search problem NP-complete?

I am learning Computational Complexity. Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that ...
-3
votes
0answers
16 views

Find the mistake in this demonstration

Let L={0^n 1^n | n>=0}, we show that L≤p VERTEX-COVER through this reduction: f(<G,k>) = { 01 if G has a k-cover; 0 otherwise} Since VERTEX-COVER ∈ NPC, L≤p VERTEX-COVER and L ∈ P. We get P=...
0
votes
3answers
47 views

Are there any FNP-complete problems with a unique solution?

Are there any FNP-complete problems where there's only one possible solution? For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest ...
0
votes
0answers
11 views

Need Help Solve an NP problem with an Approximation Algorithm

I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example. Given $n$ objects, each with $k$ possible properties, ...
-1
votes
0answers
208 views

Reduce 3-SAT to EQ-GF2 in polynomial time

The EQ-GF2 problem is the following: given a system of polynomial equations over integers modulo 2, determine if there is an assignment that satisfies all the equations simultaneously. For example, {x ...
0
votes
1answer
23 views

NP-Completeness of SAT with given hamming weight k [duplicate]

I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction. Input: A propositional formula $\varphi$ and a number $k$. Output: Yes if exists an valuation $\...
5
votes
1answer
202 views

Why the Cook-Levin reduction is not a parsimonious reduction?

In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...
2
votes
1answer
53 views

Find the class of the problem PP1 and PP2 using the information given below

Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be ...
0
votes
1answer
33 views

Does reducing a NP Hard problem to a NP problem make that NP hard problem a NP Complete problem?

I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-...
2
votes
1answer
75 views

Must all NP-complete problems have an asymptotically optimal algorithm?

According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time ...
19
votes
6answers
6k views

How to prove a problem is NOT NP-Complete?

Is there any general technique for proving a problem NOT being NP-Complete? I got this question on the exam that asked me to show whether some problem (see below) is NP-Complete. I could not think of ...
3
votes
0answers
63 views

Coloring nodes and edges in node-weighted graph

I have a graph $G$ with $n$ nodes and $O(n)$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $O(n)$. We want to color the nodes and edges ...
1
vote
0answers
37 views

Exact and approximate agorithms for independent set probem in large graphs

I have a problem which could be stated as follows: Given an unweighted undirected graph $G=(V, E)$ and positive integer $k \leq |V|$, I need to find a subset of vertices $R \subseteq V$ such that $|R| ...
1
vote
0answers
26 views

Which is the best theory of computation/automata/formal language book for practice problems(unsolved)? [closed]

I have Introduction to automata theory, languages and computation by hopcroft, rajeev motwani, jeffrey d ullman Elements of the theory of computation HR lewis Christos H papadimitriou Theory of ...
7
votes
1answer
244 views

Polynomial time algorithm for finding a maximal monotone subset

Input: Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$. Output: A subset $I\subset\{1,\dots,n\}$ of maximal size such that $(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$. ...
-1
votes
0answers
34 views

Simple measurement of complexity in Game Of Life

For a project of mine I need to measure the complexity of a game “game of life”(it is a cellular automata) after a given number of iterations. I’m not searching for a complicated way of measuring it ...
2
votes
1answer
35 views

Transitions of Turing machine in Cook Levin theorem proof

I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing ...
3
votes
1answer
113 views

Smallest 3-SAT problem that no one has been able to solve?

In number theory progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve. Is there anything similar in the field of Boolean satisfiability? ...
0
votes
0answers
27 views

Check if the given satisfying assignment of CNF formula is lexicographically the first

If there is a CNF Boolean formula in $n$ variables then the potential satisfying assignments are the binary strings of length $n$. Given a CNF Boolean formula and a satisfying assignment how ...
-1
votes
1answer
56 views

Quasilinear time algorithm for 3-SAT

Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?
3
votes
1answer
114 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
5
votes
1answer
183 views

Is there an instance of 3-SAT in less than 100 variables that no one has been able to solve?

In number theory, progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve. Is there anything similar in the field of Boolean satisfiability? ...
2
votes
1answer
67 views

How hard is random SAT?

There is plenty of research into the so-called "random SAT" problem, where we basically try to solve SAT instances with clauses chosen "at random" in some sense. There are all ...
4
votes
3answers
1k views

Rearranging strings so that the Hamming distance between them is 1

This is a question from CodeFights.com: Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at ...
2
votes
0answers
25 views

Is unary NP-Completeness equivalent to strong NP-Completeness?

I try to prove the equivalence between the two following properties of an NP-Complete problem $P$: (A) $P$ is unary NP-Complete if it is NP-Complete even if we encode the integers of the inputs with ...
0
votes
1answer
29 views

Reduction of np to npc

Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not? My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
0
votes
1answer
39 views

Karp's reduction strategy

One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction): $$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&...
1
vote
1answer
180 views

NP-completeness of satisfiability of formula over 50 variables

Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?
1
vote
1answer
32 views

Can one show NP-completeness by showing a reduction to 3SAT?

The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the ...
0
votes
0answers
16 views

Complexity class of computation of Homfly polynomial

It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
4
votes
1answer
633 views

Proofs of reduction of any hard problem

Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
0
votes
1answer
127 views

If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?

Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable. This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ ...
0
votes
0answers
24 views

Given a graph and specific VC instance, find number of variables when reducing from VC to SAT

I have question already answered from past exam, and I'm trying to figure where my logic fails. Given a graph find vertex cover of size 2. The question is how many variables are there going to be for ...
0
votes
1answer
76 views

Reduction from undecidability, decidability to decididabilty

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
1
vote
0answers
21 views

Software/library to generate Ising models for random $k$-sat problems

Could someone point me to a software/library which lets one to generate the Ising model/spin model for random $k$-sat problems or $k$-sat problem of a given structure? I understand that it will be ...
-1
votes
1answer
33 views

K-Path-Problem is in $P$ or $NPC$

Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices? How can we solve this problem? I think ...
0
votes
1answer
39 views

Is $\Pi’\propto_{poly}\Pi$ for any two NP-complete problems $\Pi,\Pi'$?

I am facing the following question: Let $\Pi$ and $\Pi$’ be two NP-complete problems, prove or refute $\Pi’\propto_{poly}\Pi$. I do not understand the meaning of this question and how to answer it. ...
1
vote
1answer
23 views

Consequences of a polytime algorithm for a decision problem reducible to 3SAT

If there is a polynomial time algorithm for a decision problem $A$, which is m-reducible to 3SAT, and 3SAT is NP-complete, does this prove that P=NP?
0
votes
1answer
67 views

Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack. I want to add a conditional constraint: $V = {...
3
votes
1answer
87 views

Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
0
votes
1answer
34 views

How to prove that the generalized assignment problem (GAP) is NP-hard?

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness? The decision version of the generalized assignment problem is to determine ...
1
vote
1answer
73 views

Is this variant of the pinwheel scheduling NP-Hard?

I wonder if the following variant of the pinwheel scheduling is NP-Hard. Given a set of n radars S = {s$_1$, s$_2$... s$_n$} and a set of m areas A = {a$_1$, a$_2$, ... a$_m$}. Each radar s $\in$ S ...
1
vote
1answer
80 views

P-NP related 3 sub-problems

This is a question on a practice final. Which of the following statements are true? If it is false, what is the underlying reason behind that? I. If 3-CNF-SAT is in P, then Clique is also in P. II. ...
0
votes
0answers
24 views

Number partition subjected to the cardinality of subset

I hope someone can take some time to consider the following problem and welcome to discuss together. Number partition problem is one of well-known NP-hard problems. Now I am considering the hardness ...
2
votes
0answers
32 views

Under ETH: $\exists$ Problem unsolvable in $2^{o(n)}$ $\Leftrightarrow^?$ 3-SAT can be represented in linear bits

It is a popular open question if there is a problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH. I recommend reading that question first. That question states that, assuming the ETH ...
3
votes
1answer
33 views

Does padding with dummy bits allow an NP-problem to be solved in fast exponential time?

Take this example mentioned here: NP-hard problems with very fast exponential-time algorithms We can create such problem by padding assuming ETH‌. Take an NP-complete problem $L$ such that $L$ is ...
2
votes
1answer
325 views

Invertability of Karp reductions

Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. I am interested in polynomial-time ...

1
2 3 4 5
28