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,607
questions
-3
votes
0
answers
35
views
Is this problem in NP. And if so why hasn't anyone used a simple problem like this to disprove P=NP [closed]
Information-
Algorithms, and you by definition cannot predict true randomness, this is a fact
2. True randomness does exist at the very foundations of matter
statement-
does P=NP. The answer is no. ...
-2
votes
0
answers
24
views
why doesn't 2SAT proof work on 3SAT
the title is quite literally my question ; why doesn't the 2sat formula work on the 3sat. I am kind of a dunce btw
0
votes
0
answers
26
views
Which one of the problems belong to P? [duplicate]
Suppose $P\neq NP$. The following problem can be solved
in polynomial time?
Given natural number $n$ and positive real numbers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$. The goal is to find
$I\...
- 1,564
0
votes
1
answer
20
views
Variant of Bounded Subset Product
Edited Version
Consider the following decision problem:
Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers each less than $n^c$ and $t$ is a target natural number,...
- 1
0
votes
0
answers
40
views
Complexity of topological sorting with a special restriction
Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:
Input variable, with in-degree $0$ and out-degree $\geqslant 1$.
A gate, with ...
- 13
1
vote
2
answers
91
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 ...
- 11
0
votes
0
answers
33
views
An Example of the Conjuction of Two NP-Complete Decision Problems Being Polynomial Time Solvable [duplicate]
Firstly, we define A and B as two decision problems with the same set of inputs.
Define a new decision problem "A AND B" as follows: The input to "A AND B" is any valid input x for ...
- 1
0
votes
0
answers
23
views
Can a problem be NP-complete and also be in complexity class FTP/XP?
P is a NPC problem. Could it be in complexity class XP/FPT or how is the relation to each other?
- 1
0
votes
1
answer
32
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
...
- 1
1
vote
1
answer
45
views
Subset sum reducible to barter economy problem?
I was given the following problem called the barter economy problem: Given a set of $n$ people $\{p_1, \ldots, p_n\}$ and a set of $m$ distinct objects $\{a_1, \ldots, a_m\}$, where each object $a_j$ ...
1
vote
2
answers
104
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 ...
1
vote
1
answer
90
views
Is there an efficient algorithm for this ecommerce optimization problem?
Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:
There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
- 15
1
vote
1
answer
37
views
Maximum Weighted coverage approximation algorithm?
I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version.
How should I modify the algorithm above to ...
- 141
1
vote
1
answer
51
views
Is this variant of multiset covering problem NP-hard?
Consider this variant of multiset covering problem.
Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$...
- 11
1
vote
1
answer
113
views
Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time
I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
- 83
0
votes
1
answer
60
views
Is the flexible bin packing problem NP-complete?
I am currently trying to figure out whether a flavor of the bin packing problem, which I call the "flexible bin packing problem" (F-BPP), is NP-complete.
Here are the definitions for the ...
2
votes
0
answers
122
views
Optimal reassociations is NP-hard?
Consider signed integers with common addition and multiplication.
Reassociation of expression is another equivalent form.
Say expressions:
...
0
votes
1
answer
44
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 ...
- 1
0
votes
0
answers
31
views
Does the following down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"?
Does the following highly down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"? If not, why not?
Marek, V. Wiktor. Introduction to Mathematics of
...
- 148
19
votes
2
answers
4k
views
Why are computability problems always written in full caps?
Maybe this is an odd question. It has always bugged me that computability problems are written in all caps, and in such an "awkward" way. SAT, 3-SAT, COLORING, 3-COLORING, PARTITION, CLIQUE, ...
- 191
0
votes
1
answer
27
views
Is minimum interval hitting problem NP-HARD?
Consider this problem:
We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
1
vote
0
answers
25
views
What is the name of this extension of the maximum independent set problem?
Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
1
vote
0
answers
57
views
What is the name of this matching problem?
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
0
votes
1
answer
127
views
reduce independent Set into independent Set of distance 4 between all vertices
I want to prove the following problem is NP-complete:
4-Spaced-Set: Assume you have a undirected graph $G=(V,E)$, and a positive integer $k$. Let's say a set of vertices $A \subseteq V$ is $4$-spaced ...
0
votes
0
answers
36
views
SMALL-FACTOR is not NPC. Is the statement true or false?
Given the SMALL FACTOR problem where:
INPUT: an integer N and an integer k
OUTPUT: yes ⇐⇒ N has a prime factor ≤ k.
I know that SMALL-FACTOR problem ∈ in NP ∩ CO-NP.
If it were NP-Complete we would ...
1
vote
1
answer
74
views
NP-Complete Proof - Using CFLP
I have formulated the below optimization problem.
\begin{align}\nonumber
\hspace{-3mm}&\text{(P) minimize}\!\sum_{i}\!\alpha_{i}w_{i}\!+\!\sum_{i}\sum_{j}\!c_{ij} p_{ij}\!\\
\text{s.t.} & \...
- 15
2
votes
1
answer
107
views
On hardness of finding dominating sets in triangle-free regular graphs
A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
- 25
1
vote
1
answer
48
views
What are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.
$VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
- 53
0
votes
1
answer
34
views
Let 3-COL-$K_4$-FREE be the decision problem that asks if a graph that doesn't contain $K_4$ admits a 3-coloring. Show that the problem is NP-complete
I'm kind of struggling with this excercise. The obvious thing to try is to show that 3-COL $\leq_p$ 3-COL-$K_4$-FREE
($\leq_p$ stands for polynomial reduction). It is clear that 3-COL-$K_4$-FREE is in ...
- 15
1
vote
1
answer
75
views
Parameterized intractability relation between split and chordal graphs
I am a research scholar currently working in computational complexity. I am working on a decision problem $P$ that is known to be W[2]-hard parameterized by the solution size on split graphs. As split ...
- 162
1
vote
1
answer
42
views
Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete
Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete
I can understand why the union and intersection of 2 NP-complete languages are true but for statement above ...
- 11
0
votes
1
answer
34
views
Hardness of finding exactly two Hamiltonian cycles in a graph
$\newcommand{\nuSwap}{\nu\textsf{-swap}}$
Two Hamiltonian cycles are different if and only if there is at least one edge they do not share.
Let $L$ consist of all graphs with exactly two Hamiltonian ...
- 129
1
vote
3
answers
47
views
Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?
Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?
Is it correct to say that it doesn't exist because clique is ...
0
votes
1
answer
37
views
Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?
I was reading a bit about $NP$-problems and how it is widely assumed that $NP\neq co$-$NP$. This also implies that the complement of $NP$-complete problems are not in $NP$.
What is known is that the ...
user154939
2
votes
0
answers
124
views
Complexity of variant of 3-SAT
This post introduces a new variant of 3-SAT called EQUAL-3-SAT where the number of clause is same as number of variables, and it is shown to be NP-complete.
I want to ask if the monotone version of ...
- 33
1
vote
0
answers
140
views
if L is in NP-Complete and its complement is also in NP does that mean L is in P? (meaning that P=NP)
$L^\complement$ = the complement of L
is it true that if
$L\in NPComplete $
and
$L\leq_p L^\complement \rightarrow P=NP$
basically asking if the following statements are correct
$if (L\in NPComplete ) ...
- 53
2
votes
1
answer
78
views
How to provide a reduction from 3SAT to domatic number problem
How to provide a reduction from 3SAT to domatic number problem.
Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, ...
- 21
2
votes
1
answer
304
views
if P = NP, does it mean that P = NP = NP-complete?
Lets assume P = NP, so all problems in NP are decidable in polynomial time,
Therefore I can solve all problems in NP in polynomial claiming P = NP = NPC.
But then, how come Σ* belongs to P = NPC ...
- 23
0
votes
0
answers
20
views
reduction from partition to N3DM or balanced 3 partition problem
I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum.
N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
- 1
1
vote
1
answer
253
views
NP-completeness of problem based on non-arbitrary instance
To prove that a problem is NP-complete, one has to show that it is both (a) in NP and that it is (b) NP-hard by reducing a known NP-complete problem to it in polynomial time.
Regarding the reduction, ...
- 113
3
votes
1
answer
48
views
Vertex Cover on Comparability Graphs
Is there anything known about the hardness of Vertex Cover on the subclass of comparability graphs? In particular, is it known whether the problem is still NP-hard?
Related Results: In "Modular ...
- 151
0
votes
2
answers
67
views
Can all NP-complete problems be reduced to NP?
I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around?
Can all NP-Complete be reduced to NP problems?
My understanding is ...
1
vote
1
answer
54
views
How can we find a shortest closed walk passing through all vertices?
How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?
We allow vertices and edges to be repeated along the walk. The ...
- 303
2
votes
2
answers
609
views
Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?
You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
2
votes
1
answer
104
views
Is the following binary quadratic integer programming NP-Hard？
I'am trying to prove the following binary quadratic integer programming problem NP hard.
$$
\min \frac{\sum\limits_{i=1}^m(u_i-\bar u)^2}{m}\text{ , where }u=Q x,Q\in\mathbb{R}^{m\times n}\\
s.t. \...
- 23
0
votes
0
answers
67
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
2
votes
1
answer
194
views
Is this path planning problem NP-complete?
Given N integers L1, L2, ... , Ln ,we have a robot that starts at (0,0) moves north on integer grid for L1 steps, then it either continues in its current direction or makes 90 degrees right turn then ...
- 4,417
0
votes
1
answer
85
views
Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + ...
0
votes
1
answer
122
views
System of equalities and inequalities is NP-hard using a reduction from 3COLORING
We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
- 25
1
vote
1
answer
44
views
Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
