Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

learn more… | top users | synonyms

0
votes
0answers
20 views

A graph is said to be in Hamiltonian cycle. Then the travelling salesman problem is? [on hold]

The graph ‘g’ with vertices {A, B, C, D, E } is said to be in Hamiltonian cycle. Then the travelling salesman problem is Heuristic NP-complete minimal spanning tree triangle inequality My ...
0
votes
1answer
71 views

Find solutions of $a + b + c$ even, $3a + 2b - 3c$ odd, $a - 7b + 8c$ odd, in polynomial time

Suppose I have a linear equation in $3$ variables $a$, $b$ and $c$. \begin{align} \begin{cases} a + b + c &= 40 \\ 3a + 2b - 3c &= 49 \\ a - 7b + 8c &= 77 \end{cases} \end{align} The ...
0
votes
1answer
19 views

Polynomial time reduction Hampath to TSP

is there a polynomial time reduction from Hamiltonian Path to TSP? If so, could you tell me? Thank you in advance! Toby
1
vote
1answer
56 views

Difference between NP-hard and NP-complete

I am struggling to tell the difference between the definitions of NP-hard and NP-complete problems. I know that NP-complete problems are NP-hard, so this tells me that $$\text{$P_1$ polynomially ...
2
votes
1answer
53 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
0
votes
1answer
33 views

Variation of TSP - Revisit Nodes

I have a problem where I have an symmetric graph and I want to find that shortest path that visits every node at least once (not exactly once). In order to solve this problem, I have found that we ...
1
vote
1answer
32 views

Optimization algorithms for Distribution and Logistics scenario

I am looking for a way to express the following logistics/distribution problem as an equation that can be run thru a solver to find an approximate solution. The problems is described as follows: ...
3
votes
0answers
58 views

Prove that Topological sort with constraints is NP-complete

This question is a followup to: Heuristics for topological sort I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total ...
0
votes
2answers
63 views

Division n items into k boxes prove that it is NP-Complete

I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem. We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < ...
0
votes
0answers
52 views

Knapsack or bin packing problem?

I have $i$ items and I should pre-packed $m$ knapsacks with identical items where only $K<n$ items can be packed. Also, we should have only one of each item in each sack. The time capacity for ...
1
vote
1answer
55 views

Still not clear why longest path problem is NP-hard but shortest path is not?

I've heard/read many times that shortest path problem is P, but longest path problem is NP-hard. But I have a problem with this: we say longest path problem is NP-hard because of graphs with positive ...
0
votes
0answers
48 views

NP-Complete: Prove this Problem is in NP (specific)

I'm trying to prove that this problem is in NP: Given $n$ dices, there are at least $m$ ways of rolling a given value $y$. Theoretically I need to argue that there is an efficient verifier for ...
1
vote
1answer
35 views

Hamiltonian path problem vs other NPC problems

If we can solve the Hamiltonian path in time $O(n^4)$ then you can solve any other NPC problem in $O(n^4)$ time. Is it true of false? I think it is false, even tho Hamiltonian path problem in NPC it ...
-1
votes
1answer
38 views

If NP-complete, prove another is also NP-complete

I've been trying to work on this problem but I don't really know where to start and can't find any resources online. Would it be possible for someone to guide me through step by step.
0
votes
1answer
39 views

Reducing Hamiltonian Path Problem to Green Path Problem

The Green Path Problem is as follows: given a graph $G$ with $n/2$ green vertices and $n/2$ red vertices, is there a simple path from $v_1$ to $v_n$ that contains every green vertex? The path can ...
0
votes
1answer
27 views

What will happen if any language in NP ∩ co-NP will become NP-complete?

I approached this question like this: Let B ∈ NP ∩ co-NP and B is also NP-complete. Then any other problem in NP can be reduced to B. Now take A ∈ co-NP. Then ~A ∈ NP which can be reduced in ...
1
vote
0answers
39 views

Is 1-in-3 SAT NP-complete if each literal must appear the same number of times as its negation?

Is 1-in-3 SAT NP-complete if each literal must appear the same number of times as its negation? That is, $x_i$ must appear the same number of times as $\neg x_i$ for all $i$. 1-in-3 SAT is a ...
0
votes
1answer
16 views

NP reductions; if $Q_1$ reduces to $Q_2$, what can we infer about $Q_2$ given what we know about $Q_1$?

I am trying to grasp this concept of reductions, which has surfaced during my study of NP-completeness. So, my textbook notes that "if $Q_1$ reduces to $Q_2$, then $Q_1$ is at least as easy as $Q_2$."...
2
votes
1answer
71 views

Reducing graph 3-coloring to 10-coloring

I am trying to show that the NP-Complete problem of 3-coloring a graph reduces to the problem of 10-coloring a graph.I have already shown how 10-coloring can be verified in polynomial time, and is ...
0
votes
0answers
29 views

Help me to find mixed chinese postman problem (MCPP) complexity

I know that MCPP is NP-Complete. Also, I have problem formulation: Chinese postman problem for mixed graphs. I was given a task to evaluate the number of operations required for a complete re-election ...
-1
votes
1answer
17 views

Does graph G contain a 100-node clique as a subgraph? Is it in P?

Although the clique problem is NP-complete, is this restricted version also considered to be NP-complete or is it actually in P? I would imagine since you are still trying to solve the clique ...
0
votes
0answers
10 views

TSP polynomial reduction to Hamiltonian Path

I have the following problem on my review sheet: A student is trying to show that HamiltonianPath is NP-complete. He states the following: A subset of the vertices of G is an efficient certificate ...
0
votes
0answers
39 views

How to argue a problem is NP

I was given an example where the last letter of the first word is the first letter of the second word and the last letter of the second word was the first letter of the third word and so on... So, ...
0
votes
1answer
21 views

Travelling salesman problem: on-paper algorithms

Are there any fast algorithms for solving the TSP on paper (without computer) given the matrix with weights of all edges. The matrix is non-symmetrical, meaning the road from $a$ to $b$ doesn't have ...
0
votes
0answers
26 views

NP inference explanation

I've been taking a look at the following question and came up with some answers but I'm wondering if there's more to it. The Question is as follows: Assume that there are proofs for the following ...
-2
votes
2answers
33 views

Traveling Salesman Number of Possible Routes

My question is: If there are 12 cities to visit, how many possible routes are? Are there (11*10*9*8*7*6*5*4*3*2*1)/2 = 19,958,400 routes?
3
votes
3answers
54 views

Algorithm/formula for computing the probability of winning a range of games

As of this post, the Golden State Warriors have 68 wins and need to win at least 5 of their remaining 7 games to break the record for most wins in a season. This article estimates the Warriors' chance ...
0
votes
0answers
17 views

Hardness of approximation for linear equations

Given a system of linear equations in n variables with coeffcients that are rational numbers, determine the largest subset of equations that are simultaneously satisable. Show that there is a ...
1
vote
1answer
33 views

Complement of SEMIPRIME is in NP

The decision version of SEMIPRIME asks if a positive integer n can be factored into 2 primes. The complement of SEMIPRIME asks if n cannot be factored into 2 primes. My understanding is that the ...
1
vote
1answer
36 views

Time Complexity of DFS

My understanding is that: 1) given a graph G with n vertices and m edges, DFS is O(n + m) 2) DFS can be used to produce a list of all simple paths between 2 vertices u and v This would mean that ...
3
votes
1answer
44 views

Why is the discrete log problem intractable?

I have read the other questions on SE on this subject and they were not helpful to me, partially because I am not familiar with advanced mathematical notation. Let me explain the way I'm thinking of ...
0
votes
0answers
44 views

What are the minimum hard constraints that cause the nurse scheduling problem to be NP-complete?

A client wishes to simplify the nurse scheduling problem to 'bypass' the NP-complete nature of this problem. He is hoping to do so by removing the requirement that there are any constraints for any ...
1
vote
1answer
56 views

On a subset sum version.

In subset sum we ask 'Given $n$ numbers in $\Bbb Z$, is there a subset of them that sums to $0$?' this is $NP$ complete. Consider variant: 'Given $n$ of degree at most $d$ polynomials in $\Bbb Z[x]$ ...
0
votes
0answers
17 views

Boolean SAT Reduction

We know that SAT is NP-complete. How can we prove P=NP if boolean SAT polynomial time reduces to evens, which is a set of natural numbers? Does it mean we can assign even numbers to each literal if it ...
0
votes
1answer
33 views

Need an example shows why SAT is NP problem

Kindly, I have two questions: (1) Are NP-hard, NP-problem, and NP-Complete are just synonyms of each other? (2) I understand that SAT is NP problem that cannot be solved in polynomial time ...
0
votes
0answers
28 views

What is an example of a search problem that is not in NP?

I feel like there should be an easy example, but I can't think of one. So, specifically, I am looking for a Yes/No search problem that is not in the class NP. When you learn about P and NP, you get a ...
1
vote
1answer
37 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

Note: I've also asked this question on StackOverflow here I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if ...
3
votes
1answer
68 views

Problems in NP but not in NPc

Are there currently any known problems that are in NP but are known not to be NP complete?
-2
votes
1answer
54 views

Is there any significant consequence if P does not equal NP-complete?

I hear a lot on these forums about how if P=NP-complete how our lives would be better, is there any significant consequence if we found P to be not equal to NP-Complete?
4
votes
1answer
81 views

Formula for all possible sums of a binary sequence

Suppose I have a sequence, where for each element I can choose one out of two numbers. I would like to find a compact formula to write all the possible sums of all the possible sequences. For example,...
2
votes
1answer
28 views

A query about reducting SAT to 3SAT when there are more than 3 literals in a clause

$C=a∨b∨c∨d∨e$ is a clause in SAT $D= (a∨b∨x)∧ (¯x∨c∨y)∧ (¯y∨d∨e)$ is the another form of C to make sure every clause has only threeliterals Is D true when C is true and false when C is false? Why? ...
1
vote
1answer
35 views

Scheduling problem on bipartite graph

Consider a bipartite graph $(G, U, V)$. Each $v$ in $V$ represents a soccer team, and each $u$ in $U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
0
votes
0answers
12 views

NP-Complete: reduce “L” the language such as circuits C1 and C2 compute the same function

I'm trying to reduce the NP-Complete language "CIRCUIT-SAT" (C is a boolean circuit that is satisfiable) to my language L, but my classmates are pointing out that i'm actually doing the opposite, ...
1
vote
0answers
97 views

Explaining Method of Pessimistic Estimators to Students

I need an alternative example for the Method of Pessimistic Estimators I need to give a lecture about the method of pessimistic estimators to computer science students. My lecture must be based on ...
1
vote
1answer
35 views

How do we decide a problem is in NP, but not in P or NPC?

As I understand, NPC set contains only the problems which can be polynomially converted into each other and which are hardest in NP set/ But how do we decide which problems are in NPC and which ...
2
votes
2answers
103 views

Can any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time? [closed]

Is it true to say that any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time?
0
votes
0answers
14 views

Np-hardness of a problem related to the knapsack problem

I am trying to know whether the following problem is NP-hard: Input: A positive number k and N pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
3
votes
2answers
54 views

Why is triangle $\in P$ (P/NP)

I'm learning about $P/NP$ and my friend used an example in which he said that if you have a triangle in an undirected graph which is basically a set of three nodes in which all pairs of nodes are ...
0
votes
1answer
29 views

What the proof, instance, and verifier mean in the definition of NP problem?

I came across a definition of NP problems: Definition. A decision problem $X ∈ NP$, if there exists a polynomial time verifier $V$ such that For every yes instance $x ∈ X$, there exists a ...
0
votes
1answer
44 views

Traveling Salesman with exceptions

Assume a regular TSP problem with n cities. However, in this particular problem, we do not have to visit all the n cities, only a specific subset of them, m, where m<=n. The cities in n but not in ...