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

learn more… | top users | synonyms

0
votes
0answers
27 views

2 Clique NP hard proof verification [on hold]

Question: prove that this language is NP-Hard. 2Clique={(G,k)|G= (V,E) contains at least two k -cliques } My Proof: (I would like to verify it's correct please) we build a mapping reduction from ...
2
votes
1answer
51 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
1
vote
1answer
18 views

Hardness of 3SAT-k

According to these scribe notes (and a paper), 3SAT-5 is NP-hard. The problem is defined to be: given a 3SAT formula, each variable occurs in at most 5 clauses. It is also proven that 3SAT-4 is ...
2
votes
1answer
25 views

Does randomness makes exponential difference?

Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the ...
1
vote
0answers
50 views

Is the multiset - subset sum problem variant not in NP?

If the input for a subset sum problem is a multiset (with repetitions) instead of a set (without repetitions), e.g. Set $a = ...
1
vote
1answer
21 views

Kth largest subset for small K

The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the ...
3
votes
1answer
21 views

What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard". I haven't seen this kind of notation before and ...
1
vote
2answers
89 views

Maximum non-intersecting subset of circles

We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$. ...
1
vote
1answer
66 views

Shortest walk that covers $k$ nodes

I have the following problem, I would like to know an efficient algorithm to solve it. Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex ...
3
votes
1answer
67 views

Knapsack problem is NP-complete - Exact cover

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
6
votes
2answers
83 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
3
votes
2answers
48 views

Can someone provide a trivial example to the “reduction” procedure used to prove hardness? [duplicate]

I cannot comprehend how you can prove hardness between two NP complete problems. For example, let X be a NP hard problem, I want to prove Y is also NP hard. I can do this by reducing X to Y, if Y is ...
0
votes
1answer
43 views

Problem A is polynomially reducible to problem B…what can we say about A and B?

This is a question on a practice final. Problem A is polynomially reducible to problem B. Which of the following statements is correct? I. If problem A is solvable in a polynomial time then problem ...
6
votes
0answers
72 views

Is finding a weight-balanced tree NP-hard?

In the following, we are considering binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of its weighted leaves. Let $T.l$ and $T.r$ be the left child and ...
0
votes
1answer
24 views

Extended knapsack: is it NP-complete? [closed]

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same: Maximize the value of ($\sum_{i=1}^n v_i \cdot x_i) + B \cdot ...
3
votes
1answer
41 views

PARTITION with 0-sum assumption

The PARTITION problem: $\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$ is well known to be NP-complete. My question: does the partition problem remain ...
0
votes
3answers
69 views

Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes. I want to show that this problem is NP-hard. Is there any ...
5
votes
0answers
59 views

NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...
1
vote
1answer
87 views

Karp reduction from 3-SAT to 3-PARTITION

I want to show that this problem is NP-complete: partition a set of 3n real numbers to n partitions of 3 number which each partition has the same sum of its members. I want to reduce 3-SAT to this ...
1
vote
2answers
50 views

Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?

I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help. The Weighted Maximum Coverage problem is ...
1
vote
1answer
47 views

Is the maximum coverage variant of Vertex Cover also NP-hard?

In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible ...
2
votes
1answer
50 views

Is ecological bin packing NP-hard?

The ACM Contest Problem 102 (HTML or PDF) can be paraphrased as: Given 3 bins each containing possibly different number of bottles of 3 colors, move the bottles so that there is one color per bin, ...
5
votes
3answers
128 views

Complexity of natural language processing problems [closed]

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any ...
8
votes
1answer
303 views

Are “Flow Free” puzzles NP-hard?

A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $\:n\times n\:$ grid graph such that each vertex is in at most one pair. $\:$ A ...
-1
votes
1answer
88 views

how to improve solution generated by greedy method for 0-1 knapsack? [closed]

I am working on 0-1 knapsack using greedy method, I have some problem in it. It's already proved that solution generated by greedy method for 0-1 knapsack is may or may not be optimal. If solution ...
6
votes
1answer
309 views

Proving NP-hardness of strange graph partition problem

I am trying to show the following problem is NP-hard. Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph Output: Partition of $G$, $G_p=(V,E_p)$ obtained ...
1
vote
1answer
76 views

Proving NP hardness of maximum sum of means of a partition into k sets

I am trying to show the following problem is NP-hard and would like some help. Inputs: Integer $k$, and unordered set of $N$ numbers, $O$ Output: the $\max \sum\limits_{S_i \in S} ...
0
votes
2answers
64 views

NP-hard proof with reduction from two known NP-hard problems

As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can ...
3
votes
1answer
80 views

The buckets of water problem

Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me). Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. ...
10
votes
2answers
189 views

Are regex crosswords NP-hard?

I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was. Can you solve the following problem in polynomial time or is ...
-1
votes
1answer
44 views

Relationship between an NP-hard problems with the subsets of them (part 2)? [duplicate]

I asked two questions about NP-hard problems here Relationship between an NP-hard problems with the subsets of them? and here Does this manner of proof for being NP-hard is true? but unfortunately ...
0
votes
1answer
93 views

NP-hardness proof, what is wrong with it?

My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is ...
6
votes
3answers
89 views

Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard?

Given a collection of non-empty subsets of $\{1,2,\ldots,N\}$ ($N$ not fixed), the problem is to find the smallest non-empty collection of subsets so that the number of distinct elements appearing ...
4
votes
1answer
29 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
5
votes
2answers
80 views

Exponential-size numbers in NP completeness reduction

In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot ...
5
votes
1answer
92 views

How hard is this constrained $n$-rooks problem?

I asked this over on math.stackexchange.com, then I found out about this forum. Suppose you have an $(n\times n)$-chessboard, together with a constraining function $C : n \times n \to 2$ where ...
1
vote
1answer
76 views

Set cover problem with constant size subset

Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?
2
votes
1answer
94 views

Monotone boolean satisfiability with at most k 1s is NP-Complete

I am to prove that monotone boolean formula satisfiability checking when at most k variables are set to 1 is an NP-Complete problem. Proving that it is in NP is easy, but I'm having difficulty ...
1
vote
1answer
67 views

if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$

I'm looking for a proof to the claim stated in the title: if $L\in NP\cap Co-NP$ is $NP$-Hard, then $NP=Co-NP$. I read the proof from my professor's recitation, but couldn't understand it, and I was ...
1
vote
2answers
242 views

Is the Calibron 12 puzzle NP-hard?

So, I was analyzing the Calibron 12 puzzle and to me it looks like a bin-packing problem. Is this puzzle actually a bin-packing problem and thus NP-hard for the perfect solution? Basically, you can ...
-2
votes
2answers
80 views

Relationship between an NP-hard problems with the subsets of them?

I am writing a paper. I have a problem and I want to prove that it is an NP-hard problem. However, for simplicity, I select a subset from my problem to prove that it is an NP-hard problem. Although I ...
0
votes
0answers
25 views

A polynomial reduction from HAMPATH to LONG-PATH [duplicate]

$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$ $\text{LONG-PATH} = \{(G,s,t,k) | \text{G has a simple path p from s to t, length(p) $\geq$ k} \}$ I'm trying ...
0
votes
2answers
41 views

Finding a 4-clique among $k$ node groups

Given a connected graph $G = (V,E)$, assume that there are partitions $\{p_0, p_1, ..., p_k\}$. Denote the partition set of a vertex $v \in V$ as $p(v)$. The neighborhood of a vertex $v$ is denoted as ...
-2
votes
1answer
81 views

NP hard: Mixed Q Horn SAT

Prove that Mixed Quantified Horn SAT problem is NP hard by reducing the Q3SAT problem to it. Q3SAT: 3SAT with possibly universally and existentially quantified variables. Mixed Quantified Horn ...
1
vote
1answer
74 views

Set of $\mathsf{NP}$-hard languages closed under set inclusion?

As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also ...
3
votes
1answer
86 views

Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard?

My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. ...
-1
votes
1answer
48 views

NP hardness of Partition

I'm trying to show that PARTITION is NP-hard. I'm not sure if what I have is correct so I'll write what I have. I tried to reduce it from SUBSET_SUM: $$PART= \{S\subset\mathbb{Z}|\exists C \subset S: ...
2
votes
1answer
139 views

Are there any PSPACE problems that don't exist in NP-Hard?

The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it ...
3
votes
1answer
35 views

Minimum weighted arithmetic mean partion?

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$. I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean ...
3
votes
1answer
42 views

Hardness of approximating hitting set

Consider the hitting set problem with $n$ elements and $m$ sets. I gather from the linked page as well as this that 1) it is NP-hard to approximate the cost of the optimal solution to a ...