Questions tagged [np-complete]
Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.
1,635
questions
1
vote
1
answer
11k
views
To prove 4-SAT CNF is NP-complete [closed]
I'm looking to prove that 4-SAT, (which will be momentarily defined) is NP-complete.
4-SAT: Given a formula in Conjunctive Normal Form, where each clause
contains exactly 4 literals, does it have a ...
- 125
3
votes
2
answers
953
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 (...
0
votes
0
answers
9
views
Is it NP-complete for deciding if a multiset of whole numbers from $A$, can sum up to $A$?
Given a set $A$ $=$ {$2,3,...$} of distinct whole numbers greater than 1, decide if $\sum_{x \in A} x \neq \sum_{y \in MULTI-SET} y$
Update: Our only input is $A$
Under the constraint of using only ...
- 321
0
votes
1
answer
32
views
If $P=NP$, then $LCP \in P$
I want to prove that if we assume $P=NP$, then we can find the longest cycle (maximal number of vertices, no repeated edges, only repeated vertex is the starting one) in an undirected graph in ...
D.W.♦
- 159k
1
vote
2
answers
114
views
NP-hardness of modified distance-colouring of graphs
Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
CommunityBot
- 1
0
votes
0
answers
16
views
Kernelization For Odd Cycle Transversal Problem on Perfect Graphs
This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
- 101
0
votes
1
answer
61
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
CommunityBot
- 1
6
votes
1
answer
909
views
Why is 3-SAT used for proving NP-Completeness so often?
I was wondering why 3-SAT is often chosen as the candidate problem from which one reduces from to prove the NP-completeness of another algorithm. I've seen it justified in places such as K&T by
...
- 193
-2
votes
1
answer
19
views
How do you show that Cosmic Kite Problem is NP complete?
A "cosmic kite" of size k consists of a clique of k nodes with a path of k nodes that unfolds from one of the nodes in the clique.
Cosmic Kite as decision problem
Input: a graph G = (V, E) ...
- 16.1k
2
votes
2
answers
599
views
Invertability of Karp reductions
Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$.
I am interested in polynomial-time ...
- 921
-1
votes
0
answers
34
views
Variation of Travelling Salesman Problem without matrix
Suppose we define a variation of the decision TSP in which instead of using a matrix to set the distances between cities ($n+1$), we assume every path ($n!$) uses completely different weights set at ...
- 1
0
votes
2
answers
163
views
( Soft question ) P vs NP - is such a situation possible?
Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements ...
CommunityBot
- 1
0
votes
1
answer
341
views
How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?
I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or ...
CommunityBot
- 1
0
votes
1
answer
104
views
On FPTAS and many one parsimonious reductions
We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.
If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?
If $\Pi_2$ has an ...
CommunityBot
- 1
1
vote
1
answer
25
views
Polynomial-Time Solvability Through NP-Completeness Reductions
Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can ...
- 565
-2
votes
2
answers
72
views
Quasi polynomial algorithm for np complete problem
I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
- 30k
1
vote
1
answer
95
views
Prove "Vertex Cover OR Clique" is NP complete
Instance: An undirected graph $G$ and a positive integer $k$
Question: Does $G$ contain a vertex cover of size $\leq k$ or a clique of size $\geq k$?
Obviously, this problem is solved by polynomial ...
- 2,522
3
votes
1
answer
70
views
Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs
Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall ...
0
votes
0
answers
33
views
If this variant of Subset Product remains NP-complete, what other inputs could give me exponential time?
Given $N$ a whole number and a set $S$ of divisors of N, where no repetition is allowed. Decide if there is a combination of divisors with a product equal to $N$.
Remove non-divisors from $S$.
Remove ...
- 321
1
vote
1
answer
135
views
How to reduce 3SAT to TwoOrMoreSAT?
I want to prove, that 2OrMoreSAT is NP-complete. It's defined as follows:
A formula is considered strongly satisfiable if there exists a model such that two or more different literals in every clause ...
- 15.5k
1
vote
1
answer
44
views
Does the Subset Product Problem remain NP-complete if repetition in S is not allowed?
Just curioius, I wanted to know when $S$ ={set of divisors of N} and we're given $N$ a target product. Our goal is to decide if a combination in $S$ has product equal to N.
Does the problem remain NP-...
- 277k
3
votes
3
answers
161
views
Are there problems in NP that would solve P vs NP, but are not NP complete
NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is if we were to find some ...
- 21
10
votes
4
answers
3k
views
Are there languages L1 ⊆ L2 ⊆ L3 when L1 and L3 are NP-Complete languages and L2 ∈ P?
Are there languages L1 ⊆ L2 ⊆ L3 where L1 and L3 are NP-Complete languages and L2 ∈ P? Would this imply P=NP?
Thanks
- 8,248
0
votes
1
answer
28
views
Is every problem which can be solved by an algorithm using polynomial space in PSPACE?
I recently learned about the definition of PSPACE problems, which are a subset of decision problems that can be solved by using polynomial space. However, one thing I don't understand is when I asked ...
- 1,048
0
votes
1
answer
1k
views
How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem
I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:
...
- 1,526
1
vote
1
answer
48
views
Complexity of this variant of the Monotone(+,2−) -SAT problem?
In this post,Monotone$(+, 2^-)$-SAT problem is defined as follows:
Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF formula $...
CommunityBot
- 1
0
votes
0
answers
29
views
Is this version of SAT NP-Complete?
Given a SAT instance such that:
Each clause is of length at most 4.
Negative literal occurs only in clauses of length=2.
Each length 2 clause has at most 1 negative literal.
Is this version of SAT ...
- 725
0
votes
0
answers
36
views
Show 3-colorable graph with hamiltonian cycle is NP-Complete
The language is :
$3COLORHC = \{<G> | \text{ G is an undirected 3-colorable graph that contains Hamiltonian cycle} \}$
I was asked to show that this language is NP-Complete.
Showing that the ...
- 15.5k
1
vote
1
answer
82
views
Is this intersection set problem NP-Hard?
Suppose we have collection of n sets $S_1, S_2, \dots, S_n$. Each set has a size of at least $k$. We know for sure that $\exists k$ sets where all of them contain the same $k$ elements; $|S_1 \cap S_2 ...
D.W.♦
- 159k
5
votes
1
answer
376
views
Why the Cook-Levin reduction is not a parsimonious reduction?
In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...
CommunityBot
- 1
0
votes
1
answer
98
views
Constructing an SAT formula from a Clique graph
We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand.
From my knowledge when ...
CommunityBot
- 1
1
vote
1
answer
826
views
Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete
I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete.
Sparse Subgraph problem:
Input: Undirected graph $G(V,E)$, two ...
CommunityBot
- 1
2
votes
1
answer
49
views
Decide whether this Problem NPC or P?
Input: A finite set A, subsets S1, . . . , Sn ⊆ A, and a number k ∈ N.
Question: Does there exist a set R ⊆ A with |R| = k such that |R ∩ Si| = |Si| for all 1 ≤ i ≤ n?
I read somewhere (without ...
- 2,911
0
votes
1
answer
25
views
Knapsack Problem for Fixed weight and Fixed price
Is the knapsack problem for a target weight, let's say 1000 for example, and a target price, let's say 10000, still an NPC problem?
- 606
9
votes
1
answer
285
views
Polynomial time algorithm for finding a maximal monotone subset
Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
...
CommunityBot
- 1
6
votes
3
answers
9k
views
Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete
I tried to solve the exercise:
Proof that determining the existence of a Hamilton Path in a bipartite graph is NP-complete
by making a bipartite graph from a general one (undirected) by inserting a ...
- 837
3
votes
1
answer
194
views
NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
CommunityBot
- 1
3
votes
2
answers
117
views
Proof that $NP \cap coNP = P$
Suppose I want to prove that $NP \cap coNP = P$. Since clearly $P\subseteq NP \cap coNP$, I need to prove the opposite direction, i.e., every problem in $NP \cap coNP$ has a polynomial-time algorithm. ...
- 3,075
0
votes
0
answers
17
views
Proof Closer String/Consensus String/Center String is NP-hard
Given are n gene sequences (words over the alphabet {A, T, C, G}), each of length m. Find a gene sequence (of length m) that minimizes the maximum distance to all given gene sequences. Here, distance ...
- 13
0
votes
1
answer
51
views
$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete
If L is NP-complete then how can I prove that $L_1$:
$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$}
is also NP- complete.
My thoughts: A reduction from (for example) SAT to L can be converted to a ...
CommunityBot
- 1
0
votes
1
answer
76
views
Knapsack with quadratic constraint
Suppose I have a variant of the knapsack problem:
$$\max_{x} \sum_{i=1}^n v_ix_i$$
$$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$
for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > ...
CommunityBot
- 1
16
votes
3
answers
9k
views
Prove NP-completeness of deciding satisfiability of monotone boolean formula
I am trying to solve this problem and I am really struggling.
A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,
$\qquad (x_1 \lor x_2) ...
D.W.♦
- 159k
1
vote
0
answers
50
views
Is it known, whether the complement of NP-hard problems is necessarily again NP-hard?
Neither could I find any counterexamples, nor could I show that if indeed the complement of NP-hard problems was NP-hard, one could deduce some unknown results from it, which would imply that it is ...
- 2,911
3
votes
1
answer
132
views
Is this an example of a natural, strictly NP-intermediate language (assuming EXP ≠ NEXP)?
In the wikipedia page for the NP-intermediate complexity class, the following observation is made:
Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this ...
D.W.♦
- 159k
2
votes
0
answers
29
views
How can the approximation algorithm of one NP-complete problem be used to prove "the class P would be the same as the class NP"?
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I had some questions about some statements in it.
Fur-
thermore, if a polynomial worst-case time ...
- 193
2
votes
1
answer
75
views
Proof that the K coloring problem is weakly or strong NP-complete?
As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete.
If an NP-complete problem is decidable ...
- 29.5k
1
vote
1
answer
64
views
Subset ${\tt XOR}$ problem
Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation.
Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
D.W.♦
- 159k
3
votes
0
answers
36
views
Approximation of the Normal Set Basis Problem
Let $B$ and $C$ be collections of finite sets. We say that $B$ is a normal basis of $C$ if for all $c\in C$ there is a pairwise disjoint subcollection of $B$ whose union is exactly $c$.
The input of ...
- 2,911
2
votes
1
answer
98
views
Problem about $NP \neq coNP$
I need to show that assuming $NP \neq coNP$ then there are 2 non-trivial languages $A$ and $B$ ($A,B \neq \emptyset, \Sigma^*$) in $NP \cup coNP$ such that there's no polynomial time reduction from A ...
- 2,911
3
votes
2
answers
164
views
Interpretation of co-NPCompleteness?
Given a Problem $A$ that has an answer $true$ if and only if both conditions $1$ and $2$ are $false$, for some conditions 1 and 2.
Whether condition $2$ is $true$ can be tested with certainty in ...
- 2,911