FAQ Database Discussion Community

algorithm,turing-machines,np,np-hard,turing-complete
this is my first question on this site. I‌ recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me. I) each NP problem can be solved in Exponential Time. II) if P=NP then NP=NP-Complete. III) Problem of factorization...

If algorithm in P, efficient way to extract solutions?

algorithm,np
Maybe this is very obvious, but if we had an algorithm in P (so this algorithm gives a yes/no answer in polynomial time), is there a more efficient way to find the solution beyond just guessing and checking? So, suppose SAT is in P (I know this is an NP-Complete...

NP and 3-SAT and One Facts

computation-theory,turing-machines,np-complete,np,decidable
any expert could help me why this sentence is True? if L ∈ NP and L ≤p 3−SAT (i.e: reduce L to 3-SAT in poly time) then L is NP-Complete. ...

How to find pattern groups in boolean array?

arrays,algorithm,pattern-matching,np,clique
Given a 2D array of Boolean values I want to find all patterns that consist of at least 2 columns and at least 2 rows. The problem is somewhat close to finding cliques in a graph. In the example below green cells represent "true" bits, greys are "false". Pattern 1...

Showing NP, NP-Completeness, or NP-Hardness

algorithm,np
Is my understanding of the three categories correct? To show a problem X is NP: Show that X can be verified deterministically in polynomial time (Or X is solvable using a NTM) To show a problem X is NP-Complete: Show that X can be verified deterministically in polynomial time(Or X...

Prove NP-completeness of CLIQUE-OR-INDEPENDENT-SET

reduction,np-complete,np,clique-problem,independent-set
First of all, I want to mention that this is my homework. However, to solve my problem I can use any literature I want. Even though I think that problem is clear from its name, I will give it description: "For given undirected graph G and given integer k, does...

Given an undirected graph G = (V, E), determine whether G is a complete graph

algorithm,graph,np
I'm pretty sure this problem is P and not NP, but I'm having difficulty coming up with a polynomially bound algorithm to solve it.