Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

learn more… | top users | synonyms

1
vote
1answer
36 views

How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
0
votes
1answer
19 views

Spanning tree with chosen leaves NP-Complete proof

I want to prove that the problem described here Spanning tree with chosen leaves is NP-Complete. Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how ...
1
vote
2answers
81 views

Proving that the language of satifiable CNF formulae with primes is NP-complete

Given the following language: $$L=\left\{\langle\phi, n\rangle \ \middle|\ \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ ...
4
votes
0answers
62 views

Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
1
vote
2answers
43 views

Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

I recognize that the subset sum problem is NP-Complete. I have a different, yet similar problem, which I'll call subset below-sum: Given a set of integers, $S$, and a target number, $n$, what is the ...
-1
votes
0answers
31 views

Proving Hamiltonian Path is NP-Complete via 3-SAT reduction

If a problem is NP-Complete, it means it is both NP (a YES solution can be verified in polynomial time) and NP-Hard (any problem in NP can reduce to it). So for example if your problem is called ...
2
votes
1answer
83 views

Stronger versions of P != NP which better express actual convictions

Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy ...
1
vote
1answer
27 views

NP-Completeness: A question about reduction and hardness [duplicate]

I am trying to understand the definition / meaning of reduction. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For ...
-1
votes
1answer
29 views

Are there any papers published proving how University Time Table Scheduling Problem is NP-Complete?

I have been researching on finding optimal solutions to generating University Time Table using Genetic Algorithm. I am searching for a Academic Paper, that properly defines the University Time Table ...
1
vote
1answer
26 views

Are these three subset sum problems hard? How to solve them?

After asking this question I was thinking about some variants of subset sum problem (SSP). The usual subset problem is the following. Instance: Given a set of $n$ integers and an integer $\sigma$. ...
0
votes
1answer
51 views

IF A is reduced to B and B belongs to NPC then where does A belongs to?

i came across a question with no proper explnation. IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P. i know why it is as ...
0
votes
0answers
9 views

Proving the Multiway cut problem is NP Complete [duplicate]

Problem Statement: Given k nodes: $$ u_1, u_2, u_3..., u_k $$ remove edges of total minimum weight that separates $u_i$ from $u_j$ for all $i != j$ for all k >= 3 I just need some help identifying ...
1
vote
1answer
49 views

Showing a problem is NP complete? Reducing CLIQUE to KITE.

I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc. The problem is, there doesn't ...
3
votes
0answers
43 views

Closed walk in planar graphs that contains k faces

Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$. Output: A shortest closed walk (one among possibly many, if exists) in $G$ using $e$ and $f$ which ...
1
vote
0answers
41 views

Is $\mathsf{GI}$ easy given input any one graph $\mathsf{NP}$-complete property?

Given graphs $G_1$ and $G_2$ that we need to decide isomorphism on and suppose we have the option to give as part of input one $\mathsf{NP}$-complete or $\#P$ property of just these two graphs (other ...
0
votes
0answers
25 views

Growing context-sensitive grammars with context-free rules

Has anyone ever considered the class of languages $X$ generated by growing context-sensitive productions which are described by context-free rules? In particular, I wonder if there is a NP-complete ...
1
vote
1answer
46 views

what does “reduce A problem to B problem in polynomial time” mean? [closed]

It is kind of NP-complete problem. For example, A problem: Given a sequence of numbers, return the maximum value within these numbers. B problem: Given a sequence of numbers, return start index ...
0
votes
0answers
23 views

Approximate algorithm to find the minimum score

Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle. Query: let $v \in P$, ...
3
votes
2answers
78 views

When proving NP-completeness do I only need one instance of a problem or all of them?

I saw a proof of reduction of hamiltonian path to spanning tree with inner vertices having degree of k. The person, who proved it, constructed a spanning tree from a hamiltonian path, basically ...
3
votes
1answer
25 views

Find permutation minimizing distance

You have a square matrix of weights $W$ and a square matrix of distances $D$. You want to find a permutation $\sigma$ minimizing $$\sum_{i,j} W_{i,j} D_{\sigma(i), \sigma(j)}$$ Is there a known ...
6
votes
1answer
164 views

Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

I read a theorem which states that: If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant ...
1
vote
1answer
41 views

NP-complete reduction for a k-dumbbell graph

A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete? Proof it is in NP: ...
0
votes
1answer
50 views

NP-complete promise problems? [closed]

Are there any good examples of promise problems that are NP complete?
1
vote
0answers
18 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, ...
-2
votes
1answer
78 views

Reduction from 3SAT [closed]

You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of ...
2
votes
1answer
214 views

Why do puzzles like Masyu lie in NP?

The puzzle is made up of (n x n) squares so when taking the problem the input size would be n. Rules of Masyu: The goal is to draw a single continuous non-intersecting loop that properly passes ...
5
votes
2answers
447 views

NP complete language having no Polytime decidable superset

Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?
-2
votes
1answer
64 views

Time Complexity and Optimization for the Algorithm?

I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity. The algorithm is as follows : Label all the vertices ...
0
votes
0answers
39 views

Poly-Time TSP Algorithm if there is constant factor approximation algorithm?

I know that a polynomial-time constant factor approximation algorithm for the general Traveling Salesman Problem does not exist unless P=NP. However, I want to prove that the TSP decision problem (is ...
2
votes
0answers
84 views

Subset minimizing the cost of a one-sided matching, involving preference orders

We're given a set of items $A=\{1,\dots,m\}$ and a set of people $B=\{1,\dots,n\}$. Each person has a preference ordering for the items in $A$. Each item in $A$ has a specific positive cost for each ...
0
votes
1answer
34 views

weighted subset exchange question

Assume there is a set {1,...,n} of person. For each person i, a set $A_i$ of items are available for exchange. A is the set of all items. The value of item j to person i is $v_{ij}$ and assume all ...
1
vote
1answer
75 views

DFA accepts common strings, reduction to NPcomplete

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and all of the $M_i$ accept some common string.} \}$ I'm trying to show that B is NP-complete. I know I have to reduce it to ...
1
vote
1answer
39 views

Conjectured NP-complete problems

Assume P != NP. Then there are many examples of problems in NP that are known not to be NP-complete, like 2-SAT, and many that are conjectured not to be NP-complete, like factorization. However, are ...
2
votes
1answer
82 views

Approximate Subset Sum with negative numbers

I am interested in the approximation version of the Subset Sum problem with negative numbers. Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states: If all numbers are ...
0
votes
1answer
39 views

Variation of the Partition Problem

Is the variation of partition problem where instead the sum of the sets only be equal to a value $B$, they could also differ by two ( i.e., the sum of one set could be $B-1$ and the other $B+1$ ) ...
2
votes
2answers
45 views

3-COL with a restriction on a number of vertices colored with a particular color

If I modify a 3-COL problem (with colors A, B, C) in a way that I now demand that at most, say, 50 vertices may be colored with color A, does the problem still remain NP-complete? I've been thinking ...
1
vote
0answers
27 views

NP-completeness of maximum-sum subtree with quadratic constraint

Intuitively, given: a graph a root node a reward mapping from node to real number a cost mapping from node to real number We want to find the tree that maximizes the reward while keeping a ...
1
vote
0answers
25 views

NP-hardness of Capacitated Minimum Spanning Tree and Price Collecting Steiner Tree on dag/tree

I am thinking about the NP-completeness of two graph problems on different graph structures. For example: The Capacitated Minimum Spanning Tree for graph is NP-hard. However, is the problem still ...
2
votes
1answer
27 views

Schaefer's dichotomy theorem and reformulating 3-literal clauses

Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would ...
6
votes
1answer
54 views

Modified Clique Problem

We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two ...
2
votes
1answer
156 views

3-SAT for variables appearing 3 times

I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity. For example, ...
1
vote
1answer
54 views

How to prove membership of NP [duplicate]

My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're ...
2
votes
1answer
335 views

Almost Hamiltonian

A graph is almost Hamiltonian if it contains a cycle that visits every node at least once and at most twice. Is the problem of determining whether a graph is almost Hamiltonian NP-complete?
0
votes
1answer
19 views

How does one enter in a boolean expression into an SAT solver?

For example, if we had an extremely large expression, how do we even first get it into the program? I can't imagine entering each clause in one by one..
1
vote
0answers
70 views

Proving NP-Completeness by reduction

I'm given a more restricted version of 3-SAT called 3-SAT-M: Problem: 3-SAT-M INPUT: A set of clauses C {c1,...,ck} over n boolean variables {x1,...,xn}, where every clause contains ...
4
votes
2answers
76 views

Can NP-Hard be converted to NP?

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem. Can an NP-Hard problem ...
1
vote
1answer
81 views

How is the complexity/size of a problem (for instance SAT) determined?

We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right? So how do we judge how many inputs there are in: $(x_1 \vee x_2 \vee ...
3
votes
1answer
71 views

NP-hardness of a scheduling problem

Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge ...
1
vote
1answer
40 views

Proof that circuit design problem is NP-hard [closed]

I have the following problem, and I want to show that it is NP-hard (or NP-complete). Consider a clause which can have OR and XOR relationship between literals, e.g. $c_1=y_1 \lor y_2 \lor (y_3\oplus ...
3
votes
1answer
38 views

For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?

In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply ...