decision problems that are at least as hard as NP-complete problems

learn more… | top users | synonyms

0
votes
1answer
16 views

Bin packing with given bin sizes, not necessarily same

I was thinking about variants of bin packing and thought of this variant wherein the given $m$ bins have size specified(not necessarily same) and we need to put $n$ objects in them. Is this still NP ...
1
vote
0answers
38 views

prove that the satisfiability problem with each clause containing at most 3 literals, denoted by ≤3SAT, is NP-complete

I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than ...
2
votes
2answers
73 views

What are the hardest problems that are in P if and only if P=NP?

I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are ...
3
votes
1answer
62 views

Why is Knapsack and ILP NP-complete

I have a question concerning several NP-hard problems and why they are (or are not NP-complete). I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and ...
0
votes
0answers
25 views

If problems P1 and P2 are known to be NP-hard, then we can conclude that P1∝P2 and P2∝P1? [duplicate]

I know the definition of NP-hard is that “a problem(P1 or P2) is NP-hard if every NP problem could be polynomially reduce to (P1 or P2)”. However, P1∝P2 means P1 could be polynomially reduced to P2, ...
1
vote
1answer
44 views

Implications of Pessiland [closed]

Consider 3COL (three colourability), Travelling Salesman, 3SAT and 2SAT. Which of these problems can be solved in polynomial time if we happen to live in world 3 (Pessiland). My Thinking - We know ...
0
votes
0answers
49 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 ...
5
votes
1answer
57 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
21 views

Minimal Steiner Tree in unweighted directed graph

I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes ...
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 . (x,y)\in\mathcal{R}\...
2
votes
1answer
31 views

Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2

I stumbled upon the following problem during my research. I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting ...
1
vote
1answer
21 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 ...
2
votes
0answers
32 views

Minimum cost edge disjoint paths - NP hard?

I've been stuck on this problem for a while now. Here it is: The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$, a ...
0
votes
1answer
78 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{...
0
votes
1answer
36 views

How is the formal definition of NP-hard equivalent to this colloquial one?

Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP". It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be ...
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$ ...
0
votes
0answers
32 views

Capacitated min-k-cut problem

In the capacitated min-$k$-cut problem we are given a graph (hypergraph) with non-negative edge (hyperedge) weights. The task is then to find a partitioning of the graph's vertices into $k$ sets of ...
3
votes
0answers
69 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 ...
2
votes
1answer
60 views

Packing sets to maximize overlap

We are given a set of $m$ elements $\{e_1,...,e_m\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in \{1,...m\}$. We ...
2
votes
1answer
35 views

Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
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 ...
2
votes
1answer
31 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 ...
5
votes
0answers
77 views

Has this graph-theoretic problem got a known name? Is it NP-hard?

I'm considering the following problem. Consider a Directed Acyclic Graph. In general, there would be some number of subgraphs that, collapsed into one node, would make it a tree. For example, in this ...
3
votes
1answer
139 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
votes
1answer
49 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
2answers
184 views

Traveling Salesman Problem with Neural Network

I was curious if there were any new developments in solving the traveling salesman problem using something like a Hopfield recurrent neural network. I feel like I saw something about recent research ...
2
votes
1answer
28 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
61 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 ...
3
votes
2answers
156 views

Can all NP-hard problems be reduced to one another?

I know that all NP-complete problems can be reduced to each other, but how about NP-hard problems? Can all NP-hard problems be reduced to one another?
1
vote
2answers
43 views

Proof that MAX CLIQUE is NP-Hard

My question is simple: does any body know where can I find the proof that MAX CLIQUE is NP-HARD? Remarks: MAX CLIQUE is the decision problem defined as follows:Given a graph $G$ and $k>0$. Does ...
1
vote
1answer
16 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 ...
0
votes
1answer
64 views

Does a problem stay NP-hard when an additional constraint is added to it?

I have the following problem $(P)'$: \begin{align*} {\rm max}_{x_1,...,x_K}\quad & \sum_{k=1}^Kf(a_k,x_k) \cr & & (P)'\cr {\rm subject\ to}\quad & 0 \le x_k \le A, k=1,\ldots,K. \end{...
1
vote
0answers
20 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
56 views

Select a subset of the columns in $3\times n$ matrix, is it NP-hard?

I want to know if this problem is NP-hard? The problem: Given a non-negative integer-valued matrix of size $3\times n$ of the form $$ \begin{bmatrix} a_1 & \ldots & a_n\\ b_1 & \ldots &...
0
votes
1answer
54 views

Test cases for graph embeddability problem

Suppose that I have a polynomial-time algorithm to solve the graph embeddability problem. $k$-embeddability problem : Given an edge-weighted and undirected graph $G = (V,E)$, can we assign ...
1
vote
1answer
90 views

How do I select a subset such that the sum and the product are greater than some value?

I have asked few days ago this question. Now I am simplifying the problem a little bit. Given two sets $A=\{a_1,\ldots,a_n\}$, and $B=\{b_1,\ldots,b_n\}$ of non-negative integers, a positive integer $...
1
vote
1answer
20 views

Can I change the input of my reductionduring the proof?

To prove that a problem $\Pi_2$ is NP-hard one has to: select a known NP-hard problem $\Pi_1$; from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and show ...
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 \...
2
votes
1answer
86 views

Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard?

I asked, incorrectly, my previous question here. I would like to thank D.W. for his answer though. He answeres that the problem is polynomial time solvable. The thing is that the cited paper shows ...
1
vote
2answers
43 views

Select the maximum number of links to satisfy the constraint on each link. How to prove is NP-hard?

Instance: $n$ non-negative real numbers $P_1,\ldots,P_n$, a positive number $k\le n$, and a positive number $\epsilon$. Question: Is there a subset $S$ of $\{1,\ldots,n\}$ of cardinality $|S|\geq k$ ...
3
votes
1answer
30 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, ...
2
votes
1answer
65 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
1
vote
1answer
96 views

Find set of non-overlapping rectangles in a 2D grid

I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned ...
4
votes
1answer
46 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
3
votes
1answer
78 views

Complexity of solving LP with a non-linear growth in variables/constraints

It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method. To solve a problem which has $k$ variables and ...
-1
votes
1answer
161 views

How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

I am studying for NP problems. To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
1
vote
0answers
50 views

Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?

I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006): Further, it is NP-hard to learn a disjunction of k ...
1
vote
1answer
50 views

NP-complete reduction for a k-dumbbell graph

A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete? Proof it is in NP: ...
0
votes
0answers
37 views

Is NP-hardness closed?

Let $X\leq Y$. If $X$ is $NP$-hard, is $Y$ $NP$-hard? I think yes, as if an $NP$ problem is reducible to $X$ in polynomial time, then surely it is also reducible to $Y$ given that $X\leq Y$. If $Y$ ...
-2
votes
1answer
88 views

Reduction from 3SAT [closed]

You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of “...