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

3
votes
2answers
43 views

Restricted Integer Programming

The integer feasibility problem is NP-complete: $Ax=b, x \geq 0, x \mbox{ integer}$ $A$ contains elements in $\mathbb{R}$ If we restrict this: $A$ contains only elements in: $\{1,0\}$ ...
1
vote
1answer
13 views

How is the complexity of algorithms to solve 3CNF (decision problem) specified? [duplicate]

For k inputs, the complexity of naive algorithm is O(2^k). I understood this one. What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement ...
-1
votes
0answers
24 views

Polynominal Reduction [duplicate]

Given two NP-Complete Problems, there exists a polynominal time reduction from A -> B. Consider: The first problem $$ a^Tx = b, x \geq 0, x \mbox{ integer} $$ The second problem $$ Ax = b, x \geq 0, ...
3
votes
1answer
18 views

Pseudo polynominal time algorithm for Np-Complete Problems

For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don't we have then a ...
0
votes
0answers
13 views

Subexponential algorithm for Np-complete problems [duplicate]

http://cstheory.stackexchange.com/a/3627/32204 Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!
2
votes
1answer
15 views

Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example: ...
0
votes
1answer
34 views

Not Hamiltonian is in NP Class? [duplicate]

I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest. From this book and other study in complexity theory, I have seen the following ...
0
votes
1answer
30 views

Satisfying assignments, twice-3SAT NP complete [duplicate]

I wanted to solve the following problem about 3SAT . The question is 1. to show if the problem is NP-complete and 2. whether the problem has two different satisfying assignments. "TWICE-3SAT Input: ...
2
votes
1answer
71 views

Questions on Graph and Hamiltonian [closed]

From this book and other study in complexity theory, I have seen the following statement: The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...
-2
votes
0answers
23 views

If L ∈ NP and L ≤p 3−SAT then L is NP-complete [duplicate]

any expert could help me why this sentence is True? if L∈NP and L≤p3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete.
3
votes
3answers
100 views

4-color to 3-color polynomial reduction

I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ? I have been searching for the right way to make this reduction for a while now. I would love some ...
2
votes
1answer
43 views

What is the implication of NP-completeness if P=NP?

If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete ...
2
votes
0answers
39 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 ...
3
votes
0answers
66 views

Relativization of NP-completeness

This is actually exercise 3.7 from "Computational Complexity: A Modern Approach". I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some ...
4
votes
0answers
22 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
17 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
23 views

SAT-3CNF - Clique [closed]

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
61 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
28 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
21 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
118 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
71 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
62 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
81 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
48 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
24 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
41 views

Subset-Sum Problem Variant with Changing Target Sum - NP Complete? [closed]

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
29 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
84 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
44 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
49 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
85 views

Reducing Exact Cover to Subset Sum

Show that the subset sum 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 ...
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
43 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
51 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
328 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
59 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
93 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
115 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
40 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
32 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
80 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
53 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
72 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
43 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 ...