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

0
votes
0answers
7 views

Reduction from 3 Dimensional Matching to Magnets

http://imgur.com/gw31LLH To elaborate a bit on MAGNETS. Imagine you have a pile of fridge magnets M and a list of words that can be spelled with the magnets called W. Given a set of magnets M and a ...
0
votes
0answers
19 views

Cyclic definition of NP-completeness [duplicate]

Trying to understand the concept of NP-completeness, I came across this pearl on Wikipedia: From NP-complete: A decision problem L is NP-complete if it is in the set of NP problems and also ...
2
votes
1answer
19 views

Complexity as it relates to verifiers of languages

So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time ...
-2
votes
1answer
46 views

NP-Complete algorithm defined on a fixed size array [closed]

Given an array, say A, with a finite definite length like N (e.g. 1000) can we define a problem to be NP-Complete without any intentional injection of NP-Completeness by something else : for example ...
1
vote
2answers
71 views

Is subset sum with a fixed target sum NP-complete?

I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a constant number? So the decision problem would look like this: Input: A collection of ...
2
votes
1answer
54 views

Partitioning NP-complete problems

Let's suppose I have an NP-complete problem A. Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete? My guess would be yes. ...
2
votes
2answers
147 views

Which NPC problems are NP Hard [duplicate]

I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete And Wikipedia defines this as ...
3
votes
1answer
36 views

Polynomial Reduction 3SAT to K-Clique

I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is: \begin{equation} 3SAT \leq_p KCLIQUE \end{equation} I am really ...
1
vote
1answer
24 views

Is the minimum weight independent dominating set np-complete in chordal graphs?

I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to ...
-1
votes
1answer
45 views

SAT reduction to prove NP completeness [closed]

Suppose you have a set of binary strings of length n, the magnitude of a string is the number of 1's it has. and you want the program to return true if there is a string of length n that has a ...
0
votes
1answer
48 views

P, NP and polynomial time reduction?

If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a ...
0
votes
1answer
42 views

Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance: Input: A digraph $G=(V,E)$ and ...
10
votes
1answer
141 views

Runtime bounds on algorithms of NP complete problems assuming P≠NP

Assume $P\neq NP$. What can we say about the runtime bounds of all NP-complete problems? i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal ...
5
votes
1answer
138 views

Reduce Vertex cover to SAT

I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT ...
0
votes
0answers
17 views

Variants of the 3-Partition problem

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known ...
2
votes
1answer
92 views

Proving NP-completeness of a graph coloring problem

Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they ...
1
vote
1answer
24 views

There is equivalence in an NP-hardness proof or not?

I want to show that some problem $P_1$ is NP-hard. I have a problem $P_2$ that is NP-complete. From an instance of $P_2$ I created in polynomial time an instance of the problem $P_1$. My question is: ...
2
votes
2answers
89 views

Hardness of mixed 3-SAT and 2-SAT formula

It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals. We can solve this ...
2
votes
1answer
93 views

Bin packing problem or not?

Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items): Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to ...
2
votes
1answer
87 views

Is this NP-completeness proof correct?

I want to prove that a problem $P_1$ is NP-complete. Let say that I want to do a reduction from SAT problem. If the instance of problem $P_1$ depends on $M$ and $N$, can I specify the sturcture of ...
3
votes
1answer
180 views

Issue understanding the reduction of SAT to 3-SAT in poly time

Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C_i$ from a $SAT$ instance containing more than 3 literals to a ...
0
votes
0answers
27 views

Balanced partition problem for N =< 60 and very large sums

I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S*N) cant run under ...
1
vote
2answers
61 views

Proving 2P2N SAT is NP-Complete

I hope I named this CNF Boolean sentence the correct way. The way I see it, a 2P2N is where each literal appears twice (or at most twice, but we can say twice without loss of generality). I am ...
1
vote
1answer
103 views

Does NP-Complete imply non-satisfiability?

I've seen a lot of text concerning the first NP-Complete problem, Boolean Satisfiability. I guess I'm confused concerning the language. It sounds to me as though the problem could be difficult to ...
3
votes
2answers
84 views

minimizing the summed cardinality of set unions

this optimization problem, I am working on, is kind of making me crazy. ;) Given is a list o of sets (with finite cardinality) of strictly positive integer values ...
2
votes
1answer
57 views

Reducing 3SAT to Triangle Cover Graph

The Triangle Cover Graph problem is this: Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also ...
1
vote
1answer
33 views

NP hard relation with NP complete

If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ? From Theory of computation of ...
1
vote
1answer
64 views

Is this path finding problem in a 01-matrix NP-complete?

The problem: Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$) Output: YES if there exists a ...
0
votes
1answer
79 views

What makes it so difficult to prove P =/≠ NP? — The subset sum issue [closed]

I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to ...
2
votes
0answers
97 views

Intractable properties of Two-factor in connected bridgeless cubic graphs

Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that ...
-1
votes
2answers
41 views

Reducing 3CNF to Clique: Why do we omit negated literals?

I have an example for a reduction of 3CNF to Clique, there is one thing I don't get about it, hopefully you could clarify it. The reduction works like this: Construct a graph G = (V, E) as ...
2
votes
1answer
21 views

Restricting longest path with 2-coloring to paths of at most constant length

I am trying to create a polynomial time algorithm for a problem defined as follows: c-ZPath(cZP) $c$ is an integer constant $\geq 1$ Input: An undirected graph $G=(V,E)$. ...
5
votes
1answer
65 views

Can we construct a Karp reduction from a Cook reduction between NP problems?

We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as ...
1
vote
1answer
60 views

Is it possible to encode an arbitrary computation as a series of NP complete problem instances? [closed]

For example, can I make a compiler that transforms a C program (Turing complete language) into a bunch of SAT instances. This encoding would be motivated as a way for specifying a problem piecemeal, ...
3
votes
0answers
26 views

PTAS vs. exact-time sub-exponential algorithms

I have recently summarized several algorithms for the maximum disjoint set problem. This problem is NP-hard, but it has both PTAS and sub-exponential algorithms. These algorithms seem to me closely ...
2
votes
1answer
62 views

0/1 Integer Programming and Karp's Reduction

I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer ...
1
vote
0answers
35 views

Is this reduction done correctly? [closed]

So we have two problems: Problem A: Given a list of positive integers, decide whether the list contains a subset adding to a given number t. Problem B: Given a list of integers, decide whether the ...
14
votes
1answer
282 views

Is regex golf NP-Complete?

As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation ...
-1
votes
1answer
54 views

How do we know that all NP problems reduce to NP-hard problems? [duplicate]

For example, how is it proven that any NP problem can reduce to subset sum, circuit satisfiability, etc.? Or could you link to a proof?
0
votes
1answer
41 views

Using approximations to optimization problems for threshold problems

Many problems in computer science come in two flavors: Optimization problem: "Find an object with the largest size". Threshold problem: "Given $n$, find an object with a size of at least $n$, or ...
4
votes
1answer
121 views

NP-complete decision problems - how close can we come to a solution?

After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant ...
1
vote
2answers
139 views

P vs NP: Assuming P = NP

Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$? I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, ...
3
votes
2answers
75 views

Hardness proof of EVEN-ODD PARTITION

The PARTITION problem is NP-complete: INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$ QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = ...
2
votes
1answer
44 views

Reduction from max-cut to min-cut

Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees. It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem ...
3
votes
1answer
101 views

How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?

Background: The Exact-3D-Matching problem is defined as follows (The definition is from Jeff's lecture note: Lecture 29: NP-Hard Problems. You can also refer to ...
10
votes
0answers
124 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
2
votes
1answer
46 views

Reduce variant of Vertex Cover to original decision-version Vertex cover problem

Consider the following variation (let us call it Q) on the Vertex Cover problem: Given a Graph G and a number K, we are asked if there is a k-cover of G so that it is the minimum cover. My question ...
1
vote
1answer
19 views

Complexity of calculating a single model versus all models of a propositional formula with a SAT solver

I have little background with SAT sovers and theoretical computer science. How can I describe the complexity of calculating all models of a propositional formula versus just the usual SAT problem of ...
1
vote
1answer
136 views

Reducing from Hamiltonian Cycle to Subgraph Isomorphism

I am reading Subgraph isomorphism problem I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article. ...
4
votes
1answer
84 views

Proving SSum is NP-Complete?

SSUM is the same as the Subset Sum Problem with the only additional requirement is all the numbers must be unique in the subset. To prove it's NP complete, the verifier is quite easy to construct ...