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
0
votes
0answers
7 views

Greedy Probabilistic Algorithm for Exact Three Cover

I have a probabilistic greedy algorithm for Exact Three Cover. I doubt it'll work on all inputs in polytime. Because the algorithm does not run $2^n$ time. I will assume that it works for some but not ...
0
votes
1answer
23 views

If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-...
1
vote
1answer
35 views

Is Monotone 3-SAT with exactly 3 distinct variables untractable?

I have given the following SAT variation: Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated....
0
votes
0answers
27 views

Is it possible to train a neural network to solve NP-complete problems?

I'm sorry if the question is not relevant, i have tried to search for articles about it but i couldn't find satisfying answers. I'm starting to learn about machine learning, neural networks etc ... ...
-2
votes
1answer
27 views

No of ways of selecting k non adjacent nodes in a graph for all k

Suppose there is an undirected connected graph with n<=38 nodes without multiple edges and self loops . We have to find the no. Of ways to select k nodes such that no two of them are adjacent for ...
1
vote
0answers
52 views

Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$. The problem is: Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that $\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}...
0
votes
2answers
16 views

Proof of Co-Problem being in NP if Problem is in NP using negated output

Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof? Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is ...
1
vote
0answers
20 views

Buckets of Water Problem - Part 2

Continuing from this question: The buckets of water problem (All the definitions can be found there, so I will not repeat them). As seen there by Yuval's answer, the problem is NP-Hard. I was ...
-1
votes
0answers
21 views

Help funding reduction for the next problem

I think this NPC and I think the way to show this is by reduction from SubsetSum, but I can't think of a way of showing this. Hints? $ApSum=$$\{(S,\{a_1,a_2,...,a_t\})|\exists U\subseteq\{1,2,...,t\}\&...
5
votes
2answers
215 views

Graph coloring variation

Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)? Problem: Given a graph $G$...
2
votes
1answer
170 views

Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

I am working on a problem defined as the following Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our ...
1
vote
1answer
33 views

Do any single-cell organisms exist that approximate NP-hard problems within a factor better than $1/2$ $log$2?

I've seen on Wikipedia; that set covering cannot be approximated in polynomial time to within a factor mentioned above. Unless $NP$ has quasipoly-time algorithms. Now, this must pertain to classical ...
0
votes
1answer
21 views

Pick elements that don't exhaust any set

The following is an NP-Complete problem: Suppose you have a collection $\mathcal{C}$ of sets, so that $A_i\in \mathcal{C}$ and $A_i$ is some set--we can suppose the elements of $A_i$ are integers. ...
0
votes
1answer
18 views

reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them. cluster problem is: there is a simple and ...
4
votes
1answer
193 views

What is the goal of studying all those NP-complete problems?

So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "...
0
votes
0answers
15 views

Bounding 0-1 matrix with k unique rows

Problem Statement: Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
2
votes
1answer
23 views

Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23): Is the size of the minimum vertex cover in $G$ at most $k$? ...
-1
votes
1answer
29 views

How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC
2
votes
0answers
63 views

Is the 3D-matching still NP-complete if all elements occur in exactly three triples?

The 3D-matching problem is known to be NP-complete even if all elements occur at most three times (see Garey&Johnson). My question: Is it also NP-complete if all elements occur in exactly three ...
-1
votes
1answer
36 views

Does 2SAT contained in SAT?

Is it true that $2 S A T \subseteq S A T ?$ and in general is $k S A T \subseteq S A T $ where k is any positive integer is true? Thanks.
0
votes
1answer
8 views

Why is the hitting set problem in NP

I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979): INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$. QUESTION: Does $S$ contains a ...
0
votes
1answer
63 views

What complexity class is the TSP problem?

Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?
0
votes
1answer
31 views

Reducing 3-coloring problem to trio representatives

A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each ...
0
votes
0answers
21 views

Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems? [duplicate]

Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems? If 3-Sat takes exponential time, then could it be possible that ...
0
votes
2answers
77 views

if A is in P and B is NP, is A ≤p B?

if A is in P and B is NP, then is A polynomial time reducible to B? Could anyone prove a prove or disprove for it?
0
votes
0answers
16 views

Given L1 and L2 in NP, if L1 transforms L2 and L2 transforms HC then L1 NP complete?

Why this Question is False ? NP-complete problems are the hardest problems in NP. if L is in NP-complete then [L must be in NP, all problems in NP can be transformed to L]. Does this mean that L2 ...
0
votes
0answers
19 views

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat?

What would the conqesquences of finding a quasi polynomial-time algorithm for 3-Sat? Would this result in their being a quasi polynomial-time algorithm for all NP-complete problems?
3
votes
1answer
46 views

Complete resolution rule for 1-in-k SAT

In CNF SAT, each clause (A or B or C or...) must contain at least one true literal. The resolution rule applies to pair of clauses who have exactly one opposite literal. (A or B or C) and (!A or D ...
0
votes
1answer
21 views

Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$?

Given an input $S$ (set of elements) find an exact three cover for a list of 3-element sets named $C$. $S$ = 1,2,3,4,5,6 $C$ = [1,2,3],[4,5,6],[3,1,2] Algorithm 1.Sort list and delete occurrences of ...
0
votes
1answer
53 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: ...
0
votes
1answer
33 views

Maximum Capacity Path Problem with constraints

I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output. The problem is: Given an undirected graph ...
1
vote
0answers
36 views

Dividing students into 4 groups based on preferences is NP-complete

Given a set of students $H$ of size $n$, and a set $E \subseteq H \times H $ of pairs of students that dislike each other, we want to determine whether it's possible to divide them into $4$ groups ...
0
votes
0answers
43 views

Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?

Decision Problem: Given a set $S$, is there at least a given $N$ $>$ $1$ amount of solutions, for an $Exact~Cover~by~3-sets$ for $C%$? $s$ = $1,2,3,4,5,6$ $c$ = $[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[...
1
vote
1answer
41 views

Languages A, B ∈ NP-complete such that A⋃B = Σ*

I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a ...
1
vote
1answer
40 views

When does Gaussian elimination solve exact 1-in-3 SAT?

Terms: A literal is a variable or its negation. A clause is a set of literals. An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 ...
4
votes
2answers
484 views

Can 3-coloring be reduced to 3-clique?

I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm ...
0
votes
0answers
16 views

Translating running times of $3$-coloring to $k$-$SAT$ complexity

Suppose there is an $O(f(n))$ algorithm for $3$-coloring a graph on $n$ vertices what does it translate to in terms of time complexity for solving $k$-$SAT$ with $m$ clauses?
4
votes
1answer
129 views

Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node. Prove that the given problem is in NP-complete. ...
3
votes
1answer
85 views

Having trouble understanding a proof of Mahaney’s theorem

I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem. I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $...
0
votes
1answer
53 views

Polynomial-time reduction of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
1
vote
1answer
47 views

Reducing independent set to triangle-free subgraph

The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$. An instance of the TFS (...
0
votes
0answers
27 views

How can I prove that the high-degree independent set problem is NP-hard?

I'm learning about NP Completeness, and I have come across the following problem The decision-version of the high-degree independent set (henceforth "HDIS") problem is stated as follows: Given a ...
1
vote
1answer
57 views

P=NP when number of inputs that give 1 is bounded by polynomial

Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, ...
2
votes
1answer
20 views

Uniquely identifying bits

Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them? Is this problem NP-Hard? For example, given the $4$ unique ...
0
votes
0answers
18 views

the correctness of 2-satisfiability problem algorithm by using implication graph

I learned finding a solution of 2-sat problem algorithm below. The point are below (1) when constructing the implication graph (2) finding there is no occurrence of a variable x and its negation x' ...
1
vote
0answers
52 views

CircuitSAT to 1-in-3SAT

This question follows Unique 3SAT to Unique 1-in-3SAT Consider an AND gate such that (A ∧ B) = C. It can be trivially expressed in 3SAT with 4 clauses and no extra variables. $$ (A ∨ B ∨ \overline{...
1
vote
0answers
27 views

How to the NP hard of a problem that search for a subset of points with maximum scores?

Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1: $[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$ Each point is assigned with a weight (possible negative): $[w(...
2
votes
2answers
148 views

Unique 3SAT to Unique 1-in-3SAT

Suppose I have a CNF formula with clauses of size 2 and 3. It has a unique satisfying assignment. It was made from a binary multiplication circuit where I multiplied two primes numbers A and B such ...
2
votes
1answer
25 views

NPC PROBLEM minimum sum of vertex coloring

For a graph G and a legal vertex-colouring ψ : V(G)→N of G, let σψ(G) be the sum of ψ(v), and set σ(G):=min σψ(G), where the minimum ranges over all valid vertex colourings of G. Prove that {(...
1
vote
1answer
41 views

Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...

1
2 3 4 5
25