Questions tagged [np-complete]

The tag has no usage guidance.

121 questions
Filter by
Sorted by
Tagged with
44 views

Problem related to Completeness : P = PC [closed]

I am learning computational complexity. So, i took some practise problems from internet. I came across 1 problem which I am not sure whether my solution is correct or not. The question is : Let us ...
81 views

63 views

93 views

NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049 For a problem I'm ...
348 views

Error in paper “Some NP-complete geometric problems”?

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems . This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
1k views

Password hashing using NP complete problems

Commonly used password hashing algorithms work like this today: Salt the password and feed it into a KDF. For example, using PBKDF2-HMAC-SHA1, the password hashing process is ...
107 views

Is Prime Bounded Quadratic Congruence NP-complete?

Bounded Quadratic Congruence: Instance: Three positive integers $a$, $b$ and $c$. Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$? Bounded Quadratic ...
53 views

NP-Complete graph problems where a special vertex is given as input?

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...
441 views

Question I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. Where $\... 1answer 114 views Can MONOTONE WSAT be in solved in polynomial time? In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the ... 0answers 133 views Practical interactive proof schemes for NP-hard problems Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ... 0answers 111 views Generalized path cover problem in DAG Let$G=(V,E)$be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ... 0answers 149 views Are there any NP-complete for continuous mathematics? [closed] Looking at this wiki page, it seems most NP-complete problems are based on discrete structures, such as graphs. What are some problems that involve real or complex analysis instead of discrete ... 2answers 848 views Isn't it trivial to represent/reduce any classical physics problem in/to a Spin-Glass language which is NP-Complete? In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ... 1answer 46 views Maximize graph with k cut edge operations I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 ... 2answers 178 views Minimising the root-set of a spanning hyperforest of a hypergraph I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a$k$-hypergraph. I describe the relevant definitions for ... 1answer 175 views Verifying that a reduction is correct Alice has a function$f: \{0,1\}^* \to \{0,1\}^*$which can be computed in polynomial time. She claims that$x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing$f$on ... 2answers 172 views Reduction of graph chromatic number to hypergraph 2-colorability I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ... 1answer 175 views Matrix Coloring under Vertical and Horizontal Constraints I'm searching for the correct name of the following NP-complete problem. I would also appreciate answers pointing to problems with similar-looking variations. The input consists of A set of ... 1answer 128 views On polytope lattice points Given a convex polytope let the width of the polytope be$d$and the farthest euclidean distance between any points in the polytope be$e$. Denote$\mathcal P(a,c)$to be the set of convex polytopes ... 0answers 168 views Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))? Actually I found that the set of context-sensitive Languages,$\mathbf{CSL}$($\mathbf{=NSPACE}(O(n))= \mathbf{LBA}$accepted languages) are not so widely discussed as$\mathbf{REG}$(regular ... 0answers 72 views Prove that finding set of$k$vertices$S$, such that$G{\setminus}S$is claw-free is NP-Complete The claw in a graph$G(V,E)$consists of a vertex$v\in V$, and it's three neighbours -$\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if$\{x_1,x_2,x_3\}$form an independent set in$G$. The problem asks us ... 1answer 187 views Fixed parameter tractable Integer Programming and$FPP$Integer programming is$NP$complete however fixed parameter tractable in number of variables. Is the fixed parameter version in parametrized analogue of$P$-complete or in parametrized analogue of$...
Let the language $L$ consist of the $k$-CNF formulas $\phi$ with the property that any satisfying assignment $x$ of $\phi$ is a Not-All-Equal (NAE) assignment, i.e. every clause of $\phi$ has at least ...