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

learn more… | top users | synonyms

2
votes
0answers
25 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
2
votes
0answers
25 views

Relativization of NP-completeness

This is actually an exercise from "computational complexity: a modern approach"(ex 3.7). I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. i need to show that that exists ...
0
votes
0answers
32 views

A Decision Problem

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following ...
4
votes
0answers
20 views

Fastest known complexity for combinatorial ILP algorithm?

I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming? I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. ...
1
vote
1answer
13 views

Reduce Clique to Vertex Cover

I read on the internet that it's possible to reduce Clique to Vertex Cover. Almost everyone use this theorem: if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of ...
1
vote
1answer
22 views

SAT-3CNF - Clique [on hold]

Could someone show me ( or give me a valuable hint) how to reduce k-Clique problem to SAT-3CNF problem ? I am able to prove reduction from SAT-3CNF to k-Clique, but in the opposite direction it's ...
-2
votes
1answer
58 views

NP-Complete Proof of k sized common set

Input: A set $U= \{w_1, w_2, \ldots, w_n\}$, subsets $S_1, S_2, \ldots, S_m$ of $U$ and integer $k$. Question: Is there a subset with $k$ elements of $U$ which intersects of every $S_i$? Which ...
2
votes
0answers
23 views

reduction of maxcut problem

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
1
vote
1answer
20 views

Hardness of 3SAT-k

According to these scribe notes (and a paper), 3SAT-5 is NP-hard. The problem is defined to be: given a 3SAT formula, each variable occurs in at most 5 clauses. It is also proven that 3SAT-4 is ...
2
votes
2answers
114 views

Direction of restriction for NP hard proves

I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that ...
1
vote
0answers
68 views

Proof of NP-completeness of a special case of longest-path problem

Problem: Longest Path Input: undirected graph $G= (V, E)$ Question: is there a path with length at least $\frac{|V|}{4}$? I know that in order to prove the simple version of $k$ longest path, we ...
1
vote
0answers
54 views

Is the multiset - subset sum problem variant not in NP?

If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g. Set $a = ...
0
votes
3answers
78 views

Given a minimum vertex cover can we find all the others in polynomial time?

Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem ...
2
votes
1answer
43 views

Complexity of a knapsack variant

Consider the following traditional integer knapsack problem: $\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$ Now ...
3
votes
1answer
22 views

What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard". I haven't seen this kind of notation before and ...
1
vote
0answers
37 views

Subset-Sum Problem Variant with Changing Target Sum - NP Complete?

Is the Subset-Sum Problem (SSP) with a changing target sum (which is dependent on the chosen subset) also NP-complete? If so, how would I reduce SSP to this or prove that it is NP-complete in another ...
0
votes
1answer
27 views

Validity of reduction (3-SAT)

I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant. This special variant works like the normal 3CNF-SAT, except every other clause ...
1
vote
1answer
29 views

Randomized and deterministic reduction

Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem. If it is hard to show deterministic reduction, then one shows a ...
0
votes
1answer
83 views

A Proof for NP-completeness

I think the following question is a mix of the Traveling Salesman Problem and the Subset-sum Problem, which makes it really hard (for me) to solve... . The problem is stated as follows: There are ...
0
votes
1answer
42 views

if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC?

if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC ? If yes then how can we generate a polynomial time verifier algorithm for the same ?
0
votes
1answer
42 views

Multiprocessor Scheduling is NP-Complete

Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m ...
3
votes
1answer
71 views

Knapsack problem is NP-complete - Exact cover

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
4
votes
1answer
27 views

What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?

I'm still in the process of grokking computational complexity. However, I came across a statement like the above in an old midterm paper I'm reviewing, and I'm not sure I completely follow its ...
1
vote
1answer
37 views

Particular techniques for NP-complete problems

Is it possible to show particular classes of techniques (for instance dynamic programming) cannot produce polynomial time algorithms to any NP-complete problem?
0
votes
1answer
43 views

Problem A is polynomially reducible to problem B…what can we say about A and B?

This is a question on a practice final. Problem A is polynomially reducible to problem B. Which of the following statements is correct? I. If problem A is solvable in a polynomial time then problem ...
3
votes
3answers
303 views

Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), ...
2
votes
1answer
51 views

If P = NP, why does P = NP = NP-Complete? [duplicate]

If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ...
-3
votes
1answer
91 views

Showing that M is NP-Complete

An instance of $M$ is a collection of sets $S_1, \dots, S_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that each item in $T$ belongs to some $S_i$, and ...
2
votes
1answer
105 views

MAX3SAT proof help? Showing that NP = coNP iff MAX3SAT is in NP

For a 3CNF $\phi$, denote by $c(\phi)$ the largest number of clauses satisfied under an assignment. Define: $\mathrm{MAX3SAT} = \{\langle\phi, k\rangle\mid c(\phi) = k \text{ and }\phi\text{ is a ...
0
votes
0answers
36 views

Reduction of specific scheduling problem to show np-completeness

Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k: Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of ...
4
votes
1answer
30 views

3 dimensionnal matching to partition transformation

We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set ...
0
votes
1answer
35 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
2
votes
1answer
48 views

NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors. Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations ...
0
votes
1answer
24 views

Can someone provide an introductory example of a certificate in complexity theory? [duplicate]

Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept. From my understanding, a certificate is used when you are trying to ...
0
votes
0answers
33 views

Request for help with two reductions

Given two graphs one needs to decide if one of them has a subgraph isomorphic to the other. Given a subset of a graph one needs to decide if the induced subgraph is triangle free. Can someone ...
4
votes
1answer
79 views

Why is Steiner Tree trivially in NP?

I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin NP. But I can't seem to wrap my head around this. Why is this so?
-1
votes
1answer
49 views

Prove NP Complete

There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete? Solution: I can prove that it ...
-1
votes
1answer
65 views

Blob detection as Constraint satisfaction problem?

In image processing I have a black and white image which is represented by matrix {0,1}, I have to find blob (a region of connected pixels) in it. I'm confused, can this problem be reduced to ...
3
votes
1answer
42 views

PARTITION with 0-sum assumption

The PARTITION problem: $\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$ is well known to be NP-complete. My question: does the partition problem remain ...
2
votes
1answer
28 views

Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar ...
1
vote
1answer
21 views

Is Bin-Packing with only 2 types of objects polynomial?

Is the following problem polynomial ? Or NP-Complete ? Problem: Bin packing with 2 types of objects. Input: $C$, the capacity of each bin, $N_a, N_b$ the numbers of objects $a$ and $b$, $w_a,w_b$ ...
0
votes
1answer
54 views

Finding vertices of a maximum clique in polynomial time [duplicate]

Say you were given a black box that solves a clique problem in constant time. You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a ...
2
votes
1answer
136 views

Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
2
votes
0answers
72 views

Is this modification of the subset-sum problem NP-complete?

Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, ...
1
vote
1answer
112 views

When is splitting a collection coins two ways NP-complete?

Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two ...
5
votes
3answers
132 views

Complexity of natural language processing problems [closed]

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any ...
1
vote
1answer
20 views

Hardness and approximation of a problem with a parameter

Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could ...
3
votes
2answers
114 views

Word tiling, where you must use each tile exactly once

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of ...
9
votes
1answer
173 views

Are all known algorithms for solving NP-complete problems constructive?

Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate? I understand that it is straightforward to turn a satisfiability ...
0
votes
0answers
15 views

When proving a problem is NP-C, how do I select another NP-C problem for the transformation? [duplicate]

I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete. Our proofs usually take the form: Given a problem $\Pi$, 1. Prove that $\Pi$ is NP. 2. Select an ...