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

8
votes
1answer
101 views

Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an ...
1
vote
1answer
35 views

How “coplanar” is a set of points?

Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to ...
1
vote
1answer
58 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?
1
vote
1answer
36 views

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

Wikipedia states on sparse languages that There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ ...
2
votes
1answer
32 views

Prove that monotone boolean satisfiability 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 ...
-4
votes
1answer
88 views

Does the Bible solve an NP-hard problem? [closed]

In the Bible, a census is taken of the 12 tribes of Israel: Simeon: 59,300 Levi: 22,000 Judah: 74,600 Issachar: 54,400 Joseph: 72,700 Benjamin: 35,400 Reuben: 46,500 Gad: 45,650 Asher: 41,500 ...
0
votes
0answers
54 views

Reduction to the constrained-shortest-path problem (CSP)

How can I reduce the subset sum problem to the CSP? Is this possible ? There are quite a few formulations of the CSP, I am talking about the following: We have an s-t graph, whose edges have costs and ...
3
votes
2answers
97 views

Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?

I read Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory. In appendix, it is claimed that In the following, we show that approximating ...
12
votes
1answer
149 views

NP-complete problems not “obviously” in NP

It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is ...
5
votes
0answers
95 views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
0
votes
1answer
107 views

Concept used in the proof [closed]

In the paper "Resolution for Quantified Boolean Formulas", I am unable to understand the proof of theorem 3.4. Please help me with the basic concept used on page 4: The concept that I am referring ...
3
votes
2answers
106 views

Need Help Reducing Subset Sum to Show a Problem is NP-Complete

I want to show that the following problem is NP-Complete: For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such ...
0
votes
1answer
72 views

Is the Berman-Hartmanis Conjecture Solved?

The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on ...
3
votes
1answer
45 views

Why do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proof

At page 277 of Sipser's Introduction to the Theory of Computation, a proof of the NP-completeness of SAT is given. The following comment is made on the trace of some machine $N$ which can decide a ...
1
vote
1answer
39 views

Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

I am confronted with task to find polynomial time complexity solution for weighted hitting set problem. I have found that usual hitting set problem is NP-complete and therefore the task seems to be ...
3
votes
1answer
39 views

Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
1
vote
1answer
58 views

Proving DPATH is NP-complete by a reduction from HAMPATH

I have a language DPATH that I'm trying to complete is NP-complete. ...
5
votes
0answers
79 views

research on OR and AND compression in SAT formulas

this is a new/advanced paper on OR and AND compression of SAT formulas, a newer area of research that seems not covered in any textbooks so far. A simple proof that AND-compression of NP-complete ...
0
votes
1answer
35 views

reducing planar 3-colouring from 3-colouring

I was reading this and I'm trying to understand how one would formally describe reducing planar 3 colouring to 3 colouring. The link pretty much describes the process but understanding the ...
1
vote
3answers
62 views

NP-completeness: Reduce to or reduce from?

Very simple question, but a mistake I make often enough that I'd love to have a standard reference. I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve ...
3
votes
3answers
306 views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
-1
votes
1answer
41 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: ...
0
votes
1answer
196 views

NP Completeness of 3-SAT problem [closed]

I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the ...
9
votes
1answer
1k views

Which NP-Complete problem has the fastest known algorithm?

In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?
1
vote
1answer
19 views

How to find partition set of a Partition Problem using its decision problem

I understand Partition Problem is NP-complete. Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to ...
3
votes
2answers
222 views

are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
1
vote
0answers
29 views

Prove that Acyclic Subgraph is NP-Hard by showing Independent Set can be reduced to Acyclic Subgraph

I am trying to prove that the Acyclic Subgraph Problem (AS) is NP-hard by showing that the Independent Set Problem (IS) is polynomially reducible to AS. AS is as follows: Given a directed graph G = ...
1
vote
1answer
73 views

How is it possible for a problem to be NP-Complete under polylog-time reductions?

I have no source for this, but I've heard people offhandedly mention problems that are NP Complete under polylog reductions (I think SAT was one of them). This confuses me - it seems to me that this ...
5
votes
1answer
108 views

Is Hamiltonian path NP-hard on graphs of diameter 2?

Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$). Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs? Perhaps some motivation is in place: the ...
6
votes
1answer
445 views

How do we know any problem is in NP-complete if we don't know all problems in NP?

A problem is NP-complete if: It is in NP. All problems in NP can reduce to it. It's number 2 that I'm concerned with here. I would be highly surprised if we knew every problem in NP. Based on ...
2
votes
1answer
158 views

Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?

In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of ...
3
votes
1answer
60 views

Negative numbers in Subset-Sum

If I have a set $A$ with positive and negative numbers, and a number to find C. It is possible to reduce the problem to one with only positive numbers in set $A$? I mean, it is possible to find a ...
1
vote
0answers
60 views

A variant of Travelling Salesman: Is it NP-complete if its sub-problems are NP-complete? [closed]

Suppose there is a travelling salesman who wants to travel through N cities in k countries(k <= N). For convenience, he will travel all the cities within a certain country and then move to another. ...
0
votes
0answers
21 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
1answer
27 views

Complexity as it relates to verifiers of languages

So I've been thinking about verifiers and a possible relation between a language's class and it's verifier complexity. From the book, "NP is the class of languages that have polynomial time ...
-2
votes
1answer
56 views

NP-Complete algorithm defined on a fixed size array [closed]

Given an array, say A, with a finite definite length like N (e.g. 1000) can we define a problem to be NP-Complete without any intentional injection of NP-Completeness by something else : for example ...
1
vote
2answers
81 views

Is subset sum with a fixed target sum NP-complete?

I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a constant number? So the decision problem would look like this: Input: A collection of ...
2
votes
1answer
81 views

Partitioning NP-complete problems

Let's suppose I have an NP-complete problem A. Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete? My guess would be yes. ...
2
votes
2answers
187 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 ...
3
votes
1answer
54 views

Polynomial Reduction 3SAT to K-Clique

I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is: \begin{equation} 3SAT \leq_p KCLIQUE \end{equation} I am really ...
1
vote
1answer
31 views

Is the minimum weight independent dominating set np-complete in chordal graphs?

I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to ...
-1
votes
1answer
47 views

SAT reduction to prove NP completeness [closed]

Suppose you have a set of binary strings of length n, the magnitude of a string is the number of 1's it has. and you want the program to return true if there is a string of length n that has a ...
0
votes
1answer
54 views

P, NP and polynomial time reduction?

If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a ...
0
votes
1answer
51 views

Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance: Input: A digraph $G=(V,E)$ and ...
10
votes
1answer
175 views

Runtime bounds on algorithms of NP complete problems assuming P≠NP

Assume $P\neq NP$. What can we say about the runtime bounds of all NP-complete problems? i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal ...
5
votes
1answer
252 views

Reduce Vertex cover to SAT

I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT ...
0
votes
0answers
23 views

Variants of the 3-Partition problem

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known ...
3
votes
1answer
159 views

Proving NP-completeness of a graph coloring problem

Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they ...
1
vote
1answer
25 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: ...
3
votes
2answers
100 views

Hardness of mixed 3-SAT and 2-SAT formula

It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals. We can solve this ...