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

learn more… | top users | synonyms

1
vote
0answers
22 views

Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes

I have a connected graph $G$ and a real-valued function $f$ on sub-graphs $G' \subseteq G$. Given a node $n \in G$ and a positive integer $s$, I am looking for the connected subgraph $G' \subseteq G$ ...
1
vote
0answers
50 views

Optimize for happiness and equality

I'm trying to solve an optimization problem: There are $N$ students who can choose to enroll into $C$ courses, each of them has a set of 3 preferences $P = \{c_1, c_2, c_3\}$ about the courses they ...
12
votes
3answers
678 views

Must an algorithm that decides a problem in NP also produce a solution?

I think I have a basic misunderstanding in the definition of a decision problem. It's widely believed that a proof of P=NP would break all modern cryptography, for example:- ...
0
votes
0answers
49 views

Why finding chromatic number is NP-Hard?

We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color . But why the coloring is ...
2
votes
1answer
28 views

Is it known whether a hypothetical P-time NP-complete decision procedure has to find a specific solution to the given constraint satisfaction problem?

Suppose a hypothetical decision procedure $A$ could solve NP-complete problems in polynomial time (of course implying $NP = P$). Many NP-complete problems take the form of constraint satisfaction, ...
2
votes
1answer
81 views

Why doesn't the decision problem for Presburger arithmetic demonstrate that $\mathsf{P} \neq \mathsf{NP}$

From Wikipedia's article on Presburger arithmetic: Then Fischer and Rabin (1974) proved that any decision algorithm for Presburger arithmetic has a worst-case runtime of at least $2^{2^{cn}}$, ...
2
votes
1answer
28 views

Are there slight modifications to NP-complete problems which reduce them to P?

Recently I revisited the infinite harmonic series and its barely diverging sum, and how removing all the composite numbers from the sum still produces a divergent series (even more barely). In ...
0
votes
0answers
35 views

Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem ...
0
votes
0answers
38 views

Proving NP-completeness

I want to prove the following problem is NP-Complete: $$\text{Given a weighted graph } G=(V,E), \text{ a vertex } v\in V \text{ and a number } K $$ The answer is YES if there exist a path of weight ...
0
votes
1answer
11 views

max degree polynomial for time complexity considerations

Is there some maximum degree for a polynomial for time complexity considerations and maybe P-NP considerations, maybe some high-degree polynomial formula identified by name, and associated with some ...
0
votes
0answers
21 views

(Proving NP Hardness) Maximizing ratio of polynomials

I have a function $\prod_{i = 1}^N \alpha_i$ $\alpha_i = \displaystyle \frac{(\sum_{j = 1}^{M} R_j x_j I_i(j))^2}{\sum_{j = 1}^{M} R_j x_j}$ The variables are $x_j$s, and $R_j$s are some positive ...
2
votes
1answer
32 views

Is $P^{SAT}$ equal to NP $\cup$ co-NP?

I have following problem: Is $P$ with a $SAT$ oracle equal to $NP \cup coNP$ assuming that $NP \neq co-NP \neq P $? I can show that $NP \subseteq P^{SAT}$ and $coNP \subseteq P^{SAT}$. But it is much ...
0
votes
1answer
18 views

Is bipartite maximal matching an NP Hard or NP Complete or neither?

Is the bipartite maximal matching problem is NP hard or NP complete or neither? If it's either can someone cite a paper saying so? Also, if its not too trivial to ask, can someone explain NP Hard and ...
3
votes
1answer
71 views

CLIQUE to UNARY-CLIQUE reduction NP complete

Assume the following Language: UNARY-CLIQUE= $\{(G=(V,E),1^k) \mid G$ is an undirected graph and there is a clique of size $k$ in $G\}$ I'm trying to determine whether this language belongs to NP ...
0
votes
1answer
20 views

Languages in coNP

if a language $L \in$ coNP, i.e. it's complement is in NP, then does L have a deterministic turing machine that decides it? i think that this is false, but am unsure how to show it? my guess is using ...
3
votes
0answers
53 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
3
votes
2answers
48 views

Proving UNIT INTERSECTION NP-complete [duplicate]

I am working on some review problems right now and am extremely stuck on how to solve problem - any help would be so appreciated. We are told to consider the following combinatorial problem: Unit ...
0
votes
0answers
27 views

Simple Turing machine problems [duplicate]

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
1
vote
1answer
107 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
2
votes
1answer
48 views

What is the “true” minimum spanning forest of a connected graph?

Normally, a minimum spanning forest of a graph G is defined as the union of minimum spanning trees of each of its components. This definition is a generalization of the minimum spanning tree of a ...
1
vote
1answer
35 views

0/1 knapsack upper bound

I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as: Knapsack max weight: 12 ...
1
vote
1answer
52 views

Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that ...
1
vote
2answers
44 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
3
votes
2answers
85 views

An easy question about NP-hard

Consider an optimization problem includes two variables. If we fix the value of one variable, then the optimization problem over the other variable is NP-hard. Can it be concluded that the original ...
1
vote
0answers
20 views

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove ...
0
votes
1answer
62 views

Need help to understand the solution for NP-completness proof (3CNF <= 0-1 integer-programming problem)

I was trying to solve problem from Cormen page 1100 34.5-2 Given an integer $m * n$ matrix A and an integer $m$-vector $b$, the 0-1 integer- programming problem asks whether there exists an integer ...
2
votes
1answer
33 views

If $P = NP \cap coNP$, can $P \ne NP$?

In Scott Aaronson's Quantum Computing since Democritus he writes on page 65: Indeed, for all we know, it could be the case that $P = NP \cap coNP$ but still $P \ne NP$. The same statement is in ...
0
votes
2answers
56 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
1
vote
0answers
29 views

If a problem in $P$ can be rewritten to $NPC$, why can this $NPC$ problem not be solved in polynomial time?

According to multiple definitions and my math professor, problems in $NP$ can be rewritten to a problem in $NPC$, including problems in $P$. Why can I solve a $P$ problem in polynomial time, but can't ...
-1
votes
1answer
18 views

Question about NP with certificate

all. I have some question about proving NP-complete The conditions of proving problem is NP-complete is following. 1) Problem is in NP 2) Problem is reducible other from NP-Complete Problem (Ex. ...
1
vote
1answer
35 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
2
votes
2answers
124 views

Is this an NP-Complete problem? (unweighted & undirected graph)

G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete. How can I show whether the algorithm is NP-complete or not?
1
vote
1answer
69 views

A decision problem that is Cook reducible to its complement

I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements. Can anyone give me ...
1
vote
1answer
45 views

What is a good example of an algorithm that is hard to parallelise?

When I have 10 computers, the factorization of a number doesn't scale along. I am not sure how much faster it would go compared to a single computer, but not 10 times faster like one would expect. ...
1
vote
1answer
17 views

Reducing a problem X to an np-complete problem Y.

Say I have a problem X that I can reduce to an NP-complete problem Y. Can I assume that problem X is in NP? Can it not be in NP?
2
votes
2answers
95 views

P vs NP - examples of P and NP

I'm currently studying 'p versus np'. Can someone help me in showing an example of a mathematical p problem and np problem? A clear worked example would be much appreciated. Many thanks in advance.
2
votes
0answers
30 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
0
votes
0answers
36 views

Clique of size $k$ or vertex with degree $\geq \log |V|$ is in $P$?

Prove that $L=\left\{ \left\langle G,k\right\rangle \mid G\mbox{ contains a vertex of degree at least }\log_{2}|V|\mbox{ or a clique of size }k\right\}$ is in $P$ ($G$ is undirected graph and $k$ is a ...
1
vote
1answer
43 views

Clarification over what NP means

I'm reading an informal definition of the decision class NP with a specific example being the standard knapsack problem and a decision variant of this problem. The example they are using is a ...
0
votes
0answers
47 views

Prove that the following Horn satisfiability problem is P-complete

Show that the following Horn satisfiability problem is P-complete: given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the Boolean satisfiability ...
0
votes
0answers
32 views

Proof the Restricted Case of CVP is P-complete

Show that the following Restricted Case of CVP is P-complete: Like CVP, except the input circuit satisfying the following conditions: All gates are placed int layers; the inputs of a gate come from ...
4
votes
1answer
71 views

Is this graph theory problem NP-Complete?

Back in college I was in an introductory Graph Theory (undergrad) class. For one assignment I was creating an algorithm to solve the following problem: Find an odd-length cycle in a directed ...
3
votes
2answers
74 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
2answers
65 views

Satisfying assignments, twice-3SAT NP complete

I wanted to solve the following problem about 3SAT . The question is 1. to show if the problem is NP-complete and 2. whether the problem has two different satisfying assignments. "TWICE-3SAT Input: ...
-2
votes
1answer
66 views

some Graph and NP Theory Problems [closed]

my instructor solve the following problem, that which of the following is into a NP Class? ...
0
votes
0answers
7 views

about concurrent open shop problem

I am working on finding bounded heuristics for a NP-hard problem. I was wondering whether there are well-known bounded solutions. The problem is formulated as follows. Given a set of $D^{(k)}(1\leq ...
1
vote
1answer
55 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
0
votes
1answer
135 views

Reduce Hamiltonian Path to CNF SAT

I'm trying to figure out how to reduce a 5 vertex graph to a Boolean equation that will answer if the graph contains a Hamiltonian path. For a Hamiltonian Path to be present in a graph: Each vertex ...
2
votes
0answers
54 views

A simple graph problem that seems NP complete

Consider an arbitrary undirected graph where each node $i$ has an arbitrary cost $c_i>0$ and each edge has a weight of 1. The objective is to select a set of edges so that the total weight of the ...
0
votes
0answers
30 views

How to prove the NP-Completeness or NP-Hardness of this MINLP problem?

I am working on an optimization problem, which is an MINLP (with binary integers). Is this MINLP an NP-Hard problem or NP-Complete problem. And how to prove the hardness or completeness? Here ...