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
2answers
35 views

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

The subset product problem was known to be $NP$-complete. I wonder if we consider the problem over ring $\mathbb{Z}_n$, as formulated below, it is still $NP$-complete? Given $t, n \in \mathbb{N}$ ...
1
vote
1answer
22 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
39 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
38 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 ...
-1
votes
0answers
13 views

How is Battleship a reduction on bin-packing? [on hold]

I am unsure how placing markers on ship locations is a reduction of the bin-packing. Any ideas?
4
votes
1answer
35 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
35 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
25 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 ...
-3
votes
0answers
11 views

Tiling problem with n x logn grid [duplicate]

If I define the tiling problem as a function that takes as input a single row of the tiling grid filled in with elements from a subset of all possible configurations of a square with 1 of 26 ...
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
79 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
97 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 ...
-1
votes
0answers
17 views

Disjoint Hamiltonian Paths NP complete proof? [duplicate]

Consider the following Disjoint Hamiltonian Paths decision problem. • Input: Graph G = (V ,E)—G may be directed or undirected. • Output: Does G contain at least two edge-disjoint Hamiltonian paths? ...
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
44 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
91 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
46 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
50 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
18 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
109 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
29 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
72 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
85 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
64 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
135 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
56 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
31 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
17 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
274 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
25 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
58 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
93 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
64 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
76 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
60 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
30 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 ...
2
votes
1answer
60 views

How do I prove Berman's theorem?

Berman's theorem states If a unary language ( a language with all the strings of the type $1^i$, $ i > 0 $ ) is NP-Complete then P = NP. I tried reducing SAT to a given unary language $L$ ...
2
votes
1answer
22 views

Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?

I use the same notation as I used in this previous question, About showing algorithmic gap instance for the Goemans-Williamson SDP The same definition continue. Given a $f : \{0,1\}^n \rightarrow ...
6
votes
1answer
158 views

How to show ExactOneSAT is NP-Complete?

$\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$ I am trying to reduce 3SAT to this ...
4
votes
1answer
24 views

MIS complexity in cubic triangle-free graphs

The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the ...
3
votes
1answer
28 views

About the Max-Cut SDP

The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum_{(i,j) \in E } (x_i -x_j)^2$ under the constraint $x_i^2 = 1, ...
1
vote
1answer
59 views

How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
0
votes
1answer
24 views

Spanning tree with chosen leaves NP-Complete proof

I want to prove that the problem described here Spanning tree with chosen leaves is NP-Complete. Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how ...
1
vote
2answers
86 views

Proving that the language of satifiable CNF formulae with primes is NP-complete

Given the following language: $$L=\left\{\langle\phi, n\rangle \ \middle|\ \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ ...
4
votes
0answers
83 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
1
vote
2answers
48 views

Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum: Given a set of integers, $S$, and a target number, $n$, what is the ...
3
votes
1answer
94 views

Stronger versions of P != NP which better express actual convictions

Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy ...