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
16 views

prove that if NP-Complete intersection Co-NP-Complete not empty then P=NP? [on hold]

prove that if NP-Complete intersection Co-NP-Complete not empty then P=NP ? can someone help me !!
0
votes
0answers
11 views

Flaw in linear programming solution for multi-commodity flow problem?

The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
-4
votes
0answers
23 views

Complexity of three subset sum variants [closed]

What is the complexity class of following three problems? (1) Given $n$ integers and another integer $c$ with promise that every subset sum is unique is there a subset that sums to $c$? (2) Given ...
6
votes
2answers
452 views

Reconciling NP and the decision problem

So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the ...
0
votes
0answers
25 views

Reduction of 3-SAT to Vertex Cover?

Can someone explain to me in the most simplest possible way, how to reduce $3-SAT$ to $Vertex\:Cover$ ? I am following the explanation here(scroll to page 4 bottom). I understand the basic setup of ...
0
votes
0answers
17 views

On subset sum instance length

Suppose we want to have a $NP$-complete subset sum instance of $m$ distinct integers from $\{-2^{n^\frac1\beta},\dots,0,\dots,2^{n^\frac1\beta}\}$ should $m=O({n^{\frac1\alpha}})$ hold where ...
2
votes
2answers
132 views

Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_i, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number. ...
0
votes
0answers
46 views

How do you reduce graph edge colouring problem to the graph node colouring problem

I know that if the nodes of a graph can be coloured by $n$ colours such that no two nodes sharing an edge have the same colour, I can also colour its edges with $n$ colours such that no two different ...
1
vote
1answer
49 views

Turing NP complete but not Karp NP complete?

Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction? Conversely is there some examples of candidate problems that have Turing reduction to SAT ...
0
votes
1answer
26 views

Finding top k which are the most different from each other

Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are. I want to ...
4
votes
1answer
50 views

Why is determining if there is a solution to a Battleship puzzle NP-Complete?

This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't ...
4
votes
0answers
40 views

find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ...
1
vote
3answers
145 views

What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete. Though implication ...
11
votes
3answers
845 views

Can any finite problem be in NP-Complete?

My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of ...
-1
votes
2answers
69 views

Is the “modular subset product” problem NP-complete?

While examining some $NP$-complete problems relating to sets of integers, a question flashed through my mind: whether the $NP$-completeness of these problems is retained when integer arithmetic is ...
1
vote
1answer
36 views

How can ships in Battleship be partitioned into B subsets, each with a capacity C?

I have been doing some research on the reduction of Battleship to bin-packing, but I do not completely understand the input to the problem from this academic paper: ...
3
votes
1answer
46 views

What is the time complexity of Summing Triples with duplicates?

Summing Triples problem is strongly $NP$-complete as shown by McDiarmid. Summing Triples problem: Input: list of 3N distinct positive integers Question: Is there a partition of the list into N ...
0
votes
1answer
49 views

show that special case of NP-complete problem is also NP-complete?

I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure ...
4
votes
1answer
41 views

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . ...
6
votes
1answer
40 views

What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...
1
vote
0answers
26 views

Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

Given the following NP-complete problem: PARTITION Input: A list of positive integers a1,a2...,an Question: Can the list be partitioned into 2 parts, A1 & A2 such that the sum of each part is ...
1
vote
1answer
20 views

About the interpretation of the SOS hardness results of the planted Max-Clique problem

One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the ...
0
votes
3answers
80 views

Size of instance after reduction

A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time. Reduction means transforming an instance of one problem $A$ to an instance ...
5
votes
1answer
101 views

Implication of Berman and Hartmanis conjecture

I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture : All $NP$-Complete languages are $p$-isomorphic. Then the book says that ...
3
votes
0answers
20 views

A particular type of SOS hardness proof

Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ ...
1
vote
1answer
47 views

If a language is X-complete, is its complement is X-complete as well?

I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ...
1
vote
1answer
93 views

Is this a well-known NP-hard problem?

Let $R = \{1, \ldots, n\}$ and $S = \{S_1, \ldots, S_m\}$ a collection of subsets of $R$ such that $R = \bigcup_{i = 1}^m S_i$ and, for $n > 3$, $$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in ...
2
votes
1answer
47 views

Is the unweighted vertex cover problem equivalent to its weighted version?

Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} ...
3
votes
0answers
66 views

Typical NP-complete/hard problems in machine learning

I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with ...
3
votes
2answers
33 views

How can we use the FPTAS for problem B to solve problem A

Given an optimization problem A which is NP-complete, and can be polynomially reduced to another optimization problem B which is also NP-complete. If we use an FPTAS to solve the reduced problem B' (A ...
1
vote
0answers
19 views

A question about SOS duality

Let us start with the optimization question, \begin{eqnarray*} min \{ c \vert c - f \in SOS_d \} \end{eqnarray*} for some function $f : \{0,1\}^n \rightarrow \mathbb{R}$ and $SOS_d $ being the cone ...
4
votes
1answer
112 views

Complexity of $n \times \log n$ tiling problem

Is there a polynomial time algorithm for an $n \times \log n$ tiling problem? For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a ...
2
votes
1answer
30 views

Is a degree-$d$ pseudo distribution always a relaxation?

The optimization problem we are generally concerned with looks like the following, \begin{eqnarray*} &\inf \{ p(x) \vert x \in K\} \\ &K = \{ x \in \mathbb{R}^n \vert q_i(x) \geq 0, i = 1,..,m ...
1
vote
1answer
83 views

Reducing co3SAT to UNIQUE-SAT

I am having trouble with this problem: Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique ...
3
votes
2answers
87 views

Is it possible to reduce the number of variables in bin packing?

The bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum_{i=1}^n y_i\\ & \text{subject to} & & B \geq 1,\\ & & & ...
0
votes
2answers
66 views

Polynomially reducing NP-Complete problem clarification

I am having trouble solving the following question. I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable. I want to show ...
3
votes
1answer
138 views

About the notation of XOR-SAT

I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf Given 3 Boolean variables $x_i, x_j, x_k$ what is supposed to be the meaning of $x_i \oplus x_j \oplus x_k$? ...
1
vote
1answer
58 views

Metaheuristic for NP-complete problem without exact algorithms other than brute-force

Computing Pure Nash Equilibria (PNE) is a Game Theory related problem. Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.). I want to design a metaheuristic ...
0
votes
1answer
40 views

Reduce knapsack to problem with {0,1}-Matrix

I'm looking for a problem, where i can reduce the knapsack feasibility problem: $$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$ to a problem, where i have a matrix ...
3
votes
1answer
28 views

Euler graph k-coloring (np-completeness proof)

I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable. Define an Euler graph as a graph that 1) is connected, and 2) has ...
0
votes
2answers
302 views

Showing that 3-colorable is NP-complete

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? ...
2
votes
1answer
26 views

A certain submatrix of the correlation polytope

I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf Firstly given that the author wanted to look at quadratic ...
0
votes
1answer
60 views

Would a polynomial-time algorithm for an NP-hard problem implies that P=NP? [duplicate]

An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.) So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would ...
6
votes
1answer
105 views

NP-complete reduction proof — graph problem

While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem: You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs ...
0
votes
1answer
70 views

NP-completeness proof via reduction

I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x ...
1
vote
1answer
89 views

CNF-SAT reduction problem variant

I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to ...
0
votes
0answers
73 views

A version of the longest simple cycle problem - NP-completeness reduction proof

I've been learning about proving NP-completeness via reduction, and came across the following problem: Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using ...
1
vote
1answer
15 views

Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

Lets say one is given a set of $m$ real polynomial equations in $n$ variables, $P_1 = P_2 = P_2 .. = P_m =0$. I understand that there is some theorem which says that if there is no solution to these ...
1
vote
0answers
19 views

About the SOS degree of a function and optimization algorithms for the function

Given a non-negative function on the hypercube $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ one says that it is of "SOS-degree" of $d$ (denoted as $deg_{SOS}(f) =d$) if $d$ is the minimum $k$ such ...
0
votes
1answer
40 views

On submultisets of given cardinality and bound that sum to $0$

Given multiset of integers $a_1,\dots,a_{m}$ where $|a_i|\leq\log^cm$ for some $c\in\Bbb R^+$. Is it $\mathsf{NP}$-complete to decide if there is a cardinality $\lceil m^\alpha\rceil$ submultiset for ...