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

learn more… | top users | synonyms

0
votes
0answers
14 views

Is the vertex cover problem NP-Hard in general graphs and in P for bipartite graphs? [on hold]

Wikipedia says that finding the minimum vertex cover is NP-Hard. However, for bipartite graphs, I can solve the maximum matching problem with Hopcroft-Karp in polytime and then, through Koenigs ...
1
vote
1answer
86 views

What is the asymptotic runtime of the best known TSP solving algorithm?

I always thought that TSP currently requires time exponential in the number of cities to solve. How, then, has Concorde optimally solved a TSP instance with 85,900 cities?!? Is this a typo? Is ...
1
vote
1answer
42 views

3-SAT to Max-2-SAT Reduction

I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck. Let me first describe it. 3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in ...
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
2answers
46 views

Is summing over all possible $k$-combinations NP-hard?

Say we have a set of numbers $A=\{a_1, a_2, \dots, a_n\}$, and we wish to sum over all possible combinations of $k$ terms to compute $$ \sum_{\substack{C \subseteq \{1,2,\dots,n\} \\ |C|=k}} \prod_{c ...
0
votes
0answers
29 views

Minimize the sum of finish times of a set of jobs [closed]

I have a scheduling problem, but have no idea how to solve this one. Questions: Given a set of jobs $J$ and a set of tasks $T$. Each of these jobs is a collection of one or more of these tasks. ...
-1
votes
0answers
27 views

What is the Unique Games Conjecture? [closed]

What is the unique game conjecture in relatively simple words? What are the consequences of proving it or disproving it? Does it has any relation to game theory? Why is there "game" in the name?
5
votes
1answer
74 views

How to compute a curious inverse

Let $M$ be a square matrix with entries that are $0$ or $1$ and let $v$ be a vector with values that are also $0$ or $1$. If we are given $M$ and $y = Mv$, we can computer $v$ if $M$ is non-singular. ...
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 ...
5
votes
4answers
116 views

Can all NP-complete cryptosystems be broken if one is broken?

I was just reading something about NP-hard problems and cryptosystems. I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) ...
4
votes
1answer
158 views

Is building this tournament fixture an NP-Hard / NP-Complete problem?

I'm curious to know if this problem is NP-Hard / NP-Complete, which I believe would mean I'm unlikely to find a polynomial-time algorithm to solve it. I have written a program which randomly ...
0
votes
1answer
96 views

Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus ...
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
1answer
91 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 ...
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 ...
3
votes
0answers
68 views

Is finding all valid nets of a polyhedron NP-hard?

Suppose I wanted to find all valid nets of a polyhedron. Is this kind of problem NP-Hard? My guess is that it is. If you were to increase the "complexity" of the polyhedron (maybe this is the number ...
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 ...
0
votes
0answers
60 views

Is this problem a knapsack problem?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
1
vote
1answer
106 views

Efficiently pick a largest set of non-intersecting line segments

Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting? Brute force we would get $2^n$ sets to check where $n$ is the ...
-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?
2
votes
1answer
91 views

3-SAT problem with number of clauses equal to number of variables

Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is ...
1
vote
1answer
78 views

Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables. If we set the $c^T$ vector of the objective $\text ...
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
1answer
99 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 ...
0
votes
1answer
50 views

NP-hardness given some reducible language

While reading a passage in an older textbook I came upon this problem which I am having difficulty in justifying whether its true or false. Is this possible? If some problem $A$ is NP-hard, and if ...
1
vote
1answer
118 views

Prove the red blue separation problem is NP-complete

Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points ...
2
votes
1answer
256 views

Question on SAT reduction

Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard. I know how to show that the complement of ...
2
votes
1answer
70 views

Proving $ \{ \langle D_1, … ,D_K \rangle : \text{ where } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $ is NP-Hard

The question (Prove L is NP-hard) was about proving that the following language is NP-hard: $$ L = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N}\text{, the } D_i \text{ are DFAs and } ...
0
votes
3answers
207 views

Having trouble proving a language is NP-complete

I'm asked to prove that, if P=NP, that 0*1* is NP-complete, but I'm having trouble going about doing it. I know it's fairly easy to prove it's NP by creating a TM to verify an input (which can be done ...
1
vote
1answer
77 views

Prove L is NP-hard

I have no clue how to prove this question. Consider the language $L = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N},$ the $D_i$ are DFAs and ${\bigcap}_{i=1}^k L(D_i) = \emptyset \}$ Prove ...
5
votes
1answer
122 views

Can Euclidean TSP be exactly solved in time better than (sym)metric TSP?

Symmetric/Metric TSP can be solved via the Held-Karp algorithm in $\mathcal O(n^2 2^n)$. See A dynamic programming approach to sequencing problems by Michael Held and Richard M. Karp, 1962. In Exact ...
2
votes
0answers
75 views

Giving an explicit reduction for IND-SET $\leq_{p}$ CNF-SAT [closed]

For a homework question I need to show an explicit reduction from independent set (of size k) to CNF-SAT. I don't have anything formal written out so I will just give an idea of what I think needs to ...
3
votes
1answer
66 views

Transforming SAT to Quadratic Programming in polynomial time

I would like to show that Quadratic Programming is NP-hard. I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the ...
3
votes
1answer
93 views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

What is the complexity of MIN-2-XOR-SAT and MAX_2-XOR-SAT? Are they in P? Are they NP-hard? To formalize this more precisely, let $$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$ where ...
2
votes
1answer
78 views

Is MIN or MAX-True-2-XOR-SAT NP-hard?

Is there a proof or reference that $\left\{\text{MAX},\text{MIN}\right\}\text{-True-2-XOR-SAT}$ is $NP$-hard, or that it (the decision version) is in $P$? Let: $$\Phi\left(\mathbf ...
4
votes
2answers
110 views

NP-hardness and FPTAS

I have a problem in understanding how to prove the following question. Let $Q = \langle\max,f,L\rangle$ be an NPO-Problem, where $f$ only supports integers. Define $$L_Q^* =\{(x_0,1^k) : \exists x . ...
8
votes
2answers
242 views

Does coNP-completeness imply NP-hardness?

Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not ...
-9
votes
1answer
1k views

Traveling Salesman - Held–Karp algorithm - BIG improvement [closed]

I think that I found a polynomial solution to TSP problem. How ever in order to prove the "think" there are many questions need to be answered. I hope you be able to help me. Part 0 - The first ...
3
votes
2answers
190 views

Find a simple path visiting all marked vertices

Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of ...
20
votes
2answers
631 views

Is Dominosa NP-Hard?

Dominosa is a relatively new puzzle game. It is played on an $(n+1)\times(n+2)$ grid. Before the game begins, the domino bones $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$ are ...
3
votes
1answer
119 views

$\mathsf{co\text{-}NP}$ and Cook reductions

Can someone help me understand the steps in this argument? There is a decision problem that is in $\mathsf{co\text{-}NP}$ (under standard Karp reductions) and is $\mathsf{NP}$-hard with respect to ...
0
votes
2answers
166 views

Showing NP-hardness of HALF-SAT

Yesterday I wrote my undergraduate exam in complexity theory. I had to leave off one question, which bugs me since then. Consider: $$ HALF-SAT = \{ \varphi \mid \varphi \text{ is a formula which is ...
5
votes
1answer
98 views

NP-Hardness reduction

I have a problem $\Pi_1$ that I want to show that is NP-hard. I know that I must find an NP-hard problem $\Pi_2$ and a polynomial time reduction $f()$ from instances of $\Pi_2$ to $\Pi_1$ such that ...
2
votes
2answers
189 views

Minimum cost closed walk in a graph

Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices? Does this problem have a name? I tried to reduce this to similar problems ...
3
votes
1answer
105 views

Is this NP-hard: min-weight n-clique in a complete n-partite graph

I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total. My problem is to find a minimum weight $n$-clique in the ...
5
votes
1answer
93 views

How hard is finding restricted assignment of 3-SAT satisfying $7/8$ of the clauses?

The PCP theorem implies (with other results) that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = ...
1
vote
0answers
25 views

Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
6
votes
0answers
474 views

Is it NP-hard to fill up bins with minimum moves?

We have $n$ bins and $m$ types of balls. The $j$th type of ball has weight $w_j$. Here $w_j$ divides $w_{j+1}$ for all $1 \leq i< m$. The $i$th bin has a target weight of $c_i$, and it has ...
2
votes
0answers
55 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing ...
1
vote
1answer
79 views

Hardness of approximation of the 3 colorability problem

If we have polynomial algorithm that $c$-approximation, $c<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements? I also have some sort of ...