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.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
23 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. ...
ChadTheVlad's user avatar
-2 votes
0 answers
22 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
ChadTheVlad's user avatar
0 votes
0 answers
19 views

Which one of the problems belong to P? [duplicate]

Suppose $P\neq NP$. Which one of the mentioned problems 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 ...
MR_'s user avatar
  • 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,...
adelta's user avatar
  • 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 ...
user779130's user avatar
1 vote
2 answers
90 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 ...
r236's user avatar
  • 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 ...
Oluchi A's user avatar
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?
Philipp's user avatar
0 votes
1 answer
30 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 ...
Sachin's user avatar
  • 1
1 vote
1 answer
41 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$ ...
redbull_nowings's user avatar
1 vote
2 answers
98 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 ...
Aditya Mishra's user avatar
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 ...
Jo Ma's user avatar
  • 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 ...
calveeen's user avatar
  • 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$...
Josh's user avatar
  • 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 ...
LargeHorse's user avatar
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 ...
thunderbird30's user avatar
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: ...
Konstantin Vladimirov's user avatar
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 ...
emily-cs's user avatar
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 ...
Geremia's user avatar
  • 142
-3 votes
0 answers
58 views

Can reversibility show that P≠NP or P=NP? [closed]

Can the fact that there are reversible operations show that P≠NP or P=NP?
Geremia's user avatar
  • 142
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, ...
Jul Wac's user avatar
  • 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 ...
Soroush Vahidi's user avatar
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. ...
Soroush Vahidi's user avatar
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 ...
Soroush Vahidi's user avatar
0 votes
1 answer
124 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 ...
andydandy 's user avatar
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 ...
user161646's user avatar
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.} & \...
Ramon's user avatar
  • 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 ...
Ankit Gayen's user avatar
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\...
Skynet's user avatar
  • 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 ...
nicoyanovsky's user avatar
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 ...
Balchandar Reddy's user avatar
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 ...
heokiu's user avatar
  • 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 ...
tomashauser's user avatar
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 ...
PatrickBateman's user avatar
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 ...
user avatar
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 ...
Anuj's user avatar
  • 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 ) ...
Skynet's user avatar
  • 53
2 votes
1 answer
77 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, ...
Hughson's user avatar
  • 21
2 votes
1 answer
297 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 ...
Shy Cohen's user avatar
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-...
user's user avatar
  • 1
1 vote
1 answer
252 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, ...
pcko1's user avatar
  • 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 ...
Henning Koehler's user avatar
0 votes
2 answers
65 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 ...
Joan Marcual's user avatar
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 ...
licheng's user avatar
  • 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 ...
Vladislav Bezhentsev's user avatar
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. \...
OvinaSun's user avatar
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 ...
Pathlessbark8's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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 + ... + ...
automatically's user avatar
0 votes
1 answer
120 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,...
staz6's user avatar
  • 25

1
2 3 4 5
33