What is Complete: Definition and 404 Discussions

In computational complexity theory, a problem is NP-complete when:

a brute-force search algorithm can solve it, and the correctness of each solution can be verified quickly, and
the problem can be used to simulate any other problem with similar solvability.The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search. "Complete" refers to the property of being able to simulate everything in the same complexity class.
More precisely, each input to the problem should be associated with a set of solutions of polynomial length, whose validity can be tested quickly (in polynomial time), such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. Conversely, a problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If any NP-complete problem has a polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC.
Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the fundamental unsolved problems in computer science today.
While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms.

View More On Wikipedia.org
Recent contents Top users
  1. B

    Complete Metric Subspaces: Are These Metric Subspaces Complete?

    Homework Statement Determine whether the following metric subspaces are complete: a) the set E of sequences containing only entries 0 & 1 in (m,||\cdot||_{\infty}) b) the unit sphere in any Banach Space Homework Equations a) for x=\{\lambda_1,\lambda_2,\ldots,\lambda_n,\ldots \}...
  2. G

    Complete by taking an arbitrary cauchy sequence

    Homework Statement (1) Prove the space \ell_\infty is complete (2)In \ell_\infty(R) , let Y be the subspace of all sequences with only finitely many non-0 terms. Prove that Y is not complete. The Attempt at a Solution (1)I can show that \ell\infty is complete by taking an arbitrary...
  3. S

    Complete residue system Question

    Hi i am doing self-study of number theory as it looks interesting and enlightening. Can someone help because I encounter a problem here.. Suppose A = {a1,a1,,,,,,,ak} is a complete residue system modulo k. Prove that for each integer n and each nonnegative integer s there exists a congruence...
  4. H

    Translate Word Puzzles as Complete Sentences

    I'm going gethergether everyeveryeveryevery thing she has done meme.
  5. S

    How Can You Simplify the Process of Calculating Partial Sums?

    Is there a particular way to get the partial sum easier than just adding the terms up? In this formula it would take a while to add up the terms if I wanted to use n=20: S_{n}+\int ^{\infty}_{n+1}f(x) dx\leqs\leq S_{n}+\int ^{\infty}_{n}f(x)dx How would I get the exact value of the sum?
  6. K

    Decreasing sequence of closed balls in COMPLETE metric space

    Homework Statement Give an example of a decreasing sequence of closed balls in a complete metric space with empty intersection. Hint 1: use a metric on N topologically equivalent to the discrete metric so that {n≥k} are closed balls. In={n,n+1,n+2,...}. Homework Equations N/A The...
  7. K

    Decreasing Sequence of Closed Balls in Complete Metric Space | Example & Hints

    Homework Statement Give an example of a decreasing sequence of closed balls in a COMPLETE metric space with empty intersection. Hint 1: use a metric on N topologically equivalent to the discrete metric so that {n≥k} are closed balls. Hint 2: In={n,n+1,n+2,...}. Consider the metric...
  8. L

    News Is a Global Government Inevitable for Solving World Issues?

    When I watch any of the speeches from the president or some other high ranking politician they almost always make remarks on how to advance the U.S.A to a superior status.Only on rare occasion do they mention Global action and advancement for everybody.Everything seems like a competitive race...
  9. L

    Why are Maxwell's Equations a complete description of EM?

    It is a well-known fact that Maxwell's Equations, along with Lorentz's Force Law, form a complete description of classical electromagnetism. But why is that? I mean, I can understand that Lorentz's Law is necessary for describing the interaction between matter and electromagnetic fields, and I...
  10. C

    Programs Time it takes to complete degree(s)

    Hello, What is the common amount of time it takes to complete an undergraduate science degree? I have heard four years and five years. What about a double major on two science fields, i.e. Chemistry and Physics; again, I have heard four years and five? To top tier graduate schools...
  11. R

    A push to an object in complete vaccum.

    Hi guys When we push an object i.e apply some force on it in complete vaccum, then due to absence of any friction; and inertia, what will happen, will the object accelerate forever because it has no reason to decelerate? Or will it move with constant speed?Why? If the object will move forever...
  12. F

    Is Mendeleev's Table Complete?

    Hi This might be a pretty stupid question to you guys, but it started to bug me. Are the elements that Mendeleev's table contains all the possible atoms that our universe contains or could there be more which we just don't know about? And if it is complete, why arent there any more...
  13. J

    Complete Amateur Needs List of Reading Material

    I'm sure this has been asked numerous times so I apologize ahead of time. I have no physics background but have been increasing interested and have read a few books in the recent months and my curiosity has only grown. So far I have read the following. In Search of Schrodinger's Cat - John...
  14. M

    Is There a Simple Solution to All Complicated Problems?

    Ok basicaly it boils down to this... Two types of problems exist, simple problems and complicated problems. The current question is do the "hard" problems have a simple answer. Ok so here is my take on this question. All problems are "hard" problems in the fact that if you run into a...
  15. M

    My complete attempt of a very difficult c problem

    [urgent] my complete attempt of a very difficult c problem Homework Statement http://u1.imgupload.co.uk/1258070400/9847_untitled.png Homework Equations *** i need to write it in C program. (not C++)The Attempt at a Solution #include <stdio.h> #include <math.h> #define N 368 int main () {...
  16. L

    Cauchy sequence without limit in a complete space?

    I know I'm doing something wrong here, but I can't find my mistake. 1) R^2 is a complete metric space under the ordinary Euclidean metric. 2) Consider the circle of radius 2, centered at the origin in R^2. 3) Construct a sequence {x_n} as follows: x_1 is at the apex of the circle (0,2)...
  17. Y

    How do we accurately measure the speed of light without frames of reference?

    As we everybody know,in this universe, every body is in motion... Then there are no frames of references..Then how could we estimate the speed of light accurately. What about the relative speed..
  18. B

    How long does it take for a high-speed train to come to a complete stop?

    A high speed train traveling at 84 kph locks its wheels and skids 84 meters before coming to a complete stop. If the rate of slowing down is constant, how many seconds will it take for the train to come to a complete stop?
  19. J

    Complete set of answers to Schaum's Tensor Calculus

    I am studying Schaum's Tensor Calculus by Kay. I am attempting to work through every solved problem (covering up the answers, first) and every supplementary problem. I am not a student. My day job is computational chemistry, so I can only do this in my spare time (whatever that is!). A...
  20. N

    Does your understanding of Quantum mechanics complete

    ... after you've taken your first undergrad course in quantum mechanics? Or does it take years , perhaps even well after you've earned your pHd in physics , for your understanding of the basic and advanced principles of quantum mechanics to be complete? Too hard to tell for me, but if I only...
  21. E

    What Is The Complete Formula Of A Lever?

    In trying to solve a problem, I was using the simple F1D1 = F2D2 as the balance point of a lever. My limited physics knowledge knew no better. My hypothetical involved using the "short side" of a lever to lift a weight on the long side of a lever. After thinking about it... I realized I...
  22. Z

    Calculate the mass of CO2 produced from the complete combustion

    Homework Statement Gasoline consists primarily of octane, C8H18 Calculate the mass of CO2 produced from the complete combustion of 3.79 L (1.00 gallon) of gasoline (assume octane, density = 0.756 g/mL) with excess O2 The Attempt at a Solution The balanced chemical formula would be: 2C8H18 +...
  23. M

    How long will it take the rabbit to come to a momentary complete stop

    Homework Statement Using the equations from question 1 determine how long it will take the rabbit to come to a complete momentary stop. Homework Equations X= 30cm + (-40 cm/s)t + (24 cm/s^2)t^2 V= (-40cm/s) + (12 cm/s^2)t V^2= (-40 cm/2)^2 + 2(12 cm/s^2)[X-30cm] The Attempt at...
  24. F

    Residue Problem: Seeking Alternative Solutions

    The problem (#3) can be found here:http://img198.imageshack.us/i/img002lf.jpg/" It would be helpful if someone could look over my solution (found here:http://img525.imageshack.us/i/img001of.jpg/" ) and also it would be helpful if anyone had a different approach to this problem. Thanks
  25. L

    Is Every Cauchy Sequence in the Real Numbers Convergent?

    Hello, why the set of all real numbers is complete metric space with euclidean metric? I know, that metric space is complete iff all sequences in it converges. But 1,2,3,4,... diverges. Thanx
  26. A

    Capacitor Charger | LED Illuminate when Complete

    I'm looking to assemble a capacitor charger in a nice, durable enclosure. I already have the DC to HV DC converter. I'm just looking, now, for a way to indicate when the capacitor is fully charged, practically identical to how a flash-enabled camera indicates when its capacitor is charged and...
  27. W

    Completeness of \ell^1: Proving Convergence of Cauchy Sequences

    Homework Statement Prove that \ell^1, the space of all (real) sequences v = \{v_k\} such that \sum|x_k| < \infty , is complete. Homework Equations \ell^1 is a normed space with the norm ||x|| = \sum |x_k| The Attempt at a Solution Let v_n be a Cauchy sequence of sequences in...
  28. L

    Wanted: complete errata sheet for quantum mechanics demystified

    yo. today I got "quantum mechanics demystified", and I heard it has a lot of typos. Can you list them all for me (in tex if possible)?
  29. O

    Does anyone else think this article is complete baloney

    http://discovermagazine.com/2009/may/01-the-biocentric-universe-life-creates-time-space-cosmos/article_view?b_start:int=0&-C=
  30. T

    Relation for Inner Product with States from a Complete Set

    Hi. I've found the following relation (in a book about the qm 3-body scattering theory): <\Omega^{\pm}^{\dagger} \Psi_n|p>= ... = 0 where |p> is a momentum eigenstate. So it is shown, that the inner Product is zero. Then they conclude that \Omega^{\pm}^{\dagger}|\Psi_n> = 0 because the...
  31. J

    Complete this sequence... A,T,I,I,G,Q,F,D....

    Can anyone help me to complete this sequence.. A,T,I,I,G,Q,F,D... thanks in advance:smile:
  32. B

    Complete Inelastic collision & Force

    Homework Statement Raindrops of mass 0.99 mg fall vertically at a constant speed of 9.0 m/s, striking a horizontal skylight at the rate of 1000 drops/s and draining off. The window size is 17.0 cm x 25.0 cm. Assume the collisions of the drops with the window are completely inelastic...
  33. R

    Neuroscience, complete newbie about it, one of my interests too (ironicly)

    Yes, I know I can easily google this... but forums is more fun :smile: Is the job title "Neuroscientist" a vague term, is it sort of like engineering? What type of engineer? How would I get started about researching the brain? Job prospects? Is it like psychology, that if you only had a...
  34. Y

    Where i can find complete data for material elastic constants?

    Where i can find complete data for material elastic constants?? I need elastic constants, piezoelectric coefficients & permittivity for different semiconductor alloy? Someone could kindly help...
  35. pellman

    What is meant by a complete solution ?

    What is meant by a "complete solution"? What is meant by a complete solution of a system of ODEs? (Such, as for example, in the Hamiltonian formulation of an N-particle system) I am trying to relate the definition here...
  36. M

    Where can I find a complete logarithmic formulas worksheet or tutorial?

    Homework Statement I need to find as much as a complete logarithmic formulas worksheet or tutorials I have not been in school for atleast 2 semesters and the class I am taking right now makes use of the basic logarithmic functions, not to complicated from what the teacher has told us. I do...
  37. L

    Difference between a boolean algebra and a complete lattice?

    What is the difference between a boolean algebra and a complete lattice? What are their similarities?
  38. A

    Question about 4-vectors/tensors from a complete novice

    Is any distinction made between an expression like A^\nu A_\mu and one that looks like A^\mu A_\mu? I can justify something like this to myself through some vague hand-waving and mention of a phrase like "just dummy indices," but this isn't convincing even to me...and I'm making the argument...
  39. T

    Complete to orthonormal basis question

    i got these vectors which are othronormal v1 (1/2,-1/2,1/2,-1/2) v2 (-1/2,1/2,1/2,-1/2) i need to compete them into orthonormal basis i did row reduction on them and added these independant vectors to the group v3(1,0,0,0) v4(0,1,0,0) now all four vectors are independant...
  40. A

    Average value of AC over a complete cycle is always zero

    Homework Statement Statement 1: Average value of AC over a complete cycle is always zero. Statement 2: Average value of AC is always defined over half cycle. We need to tell whether these two statements are right, and if 1 is right then whether 2 is its explanation. Homework...
  41. I

    Help, AS level physics for a complete beginner

    hello everyone, i'd be really appreciative of some help. I'm doing as physics and have never done proper physics before therefore I'm finding it quite hard. we are doing about waves at the moment and was wondering about a couple of things:- 1st - how to calculate frequency using the time base...
  42. I

    Help, AS level physics for a complete beginner

    hello everyone, i'd be really appreciative of some help. I'm doing as physics and have never done proper physics before therefore I'm finding it quite hard. we are doing about waves at the moment and was wondering about a couple of things:- 1st - how to calculate frequency using the time base...
  43. A

    Math Trying to complete a minor in math

    I'm currently a first year (Life Science) undergraduate in a Canadian University and I was thinking of trying to complete a minor in math. I kind of like math and it does somewhat interest me; but lately I have become lazy, I feel like I was much more school orientated in high school. I'm am...
  44. P

    Help me complete this question please

    This is from the M1 review excercise Edexcel. I've managed to do a) b) and c) and but now I'm completely stuck. I'm no particular wizz at mechanics and getting stuck at d) means I'm suddenly uncertain about e) and f) :(. Here is the question: In this question i and j are horizontal unit...
  45. D

    Sakurai 1.17 - Operators and Complete Eigenkets

    I'm pretty sure this is correct, but could someone verify for rigor? Problem Two observables A_1 and A_2, which do not involve time explicitly, are known not to commute, yet we also know that A_1 and A_2 both commute with the Hamiltonian. Prove that the energy eigenstates are, in general...
  46. S

    Mit physics 2008 vids (not complete yet)

    heres a link http://techtv.mit.edu/collections/8012/videos of 9 current mit intro physics videos. i don't know if they have been posted or not.. somewhat hard to see the board, but if u listen u can make it out. -shoobs
  47. H

    Solving Incomplete Integral: Easy Steps and Tips | Andishe9

    Hi all, can anybody complete my answer?(I'm unable to solve the second part of the integral) problem and answer(incomplete) : [PLAIN]www.andishe9.com/integral.bmp[/URL] thanks and excuse me for english;)
  48. W

    Metric space of all bounded real functions is complete

    Homework Statement Let X be a non-empty set and let C be the set of all bounded real functions defined on X, with the metric induced by the supremum norm: d(f,g) = ||f - g|| = sup |f(x)-g(x)| , x in X. Show that the metric space (C,d) is complete. Hint: if \{f_{n}\} is a cauchy sequence...
  49. F

    Equivalence of Metrics and Completeness in Metric Spaces

    Homework Statement We say that two metrics d, d' on a space S are equivalent if each "dominates" the other in the following sense: there exist constants M, M'>0 such that d'(x,y)<=M' d(x,y) and d(x,y)<=M d'(x,y) for all x,y in S. If metrics d, d' are equivalent, prove that (S,d) is...
  50. F

    Discover the Best Books for Understanding Quantum Mechanics | Beginners Welcome!

    Dear Users Hello! MY First Post I want to make rock solid concepts in Quantum Mechanics General not any specific branch of Quantum Mechanics like Quantum Computing,Perturbation Theory etc etc Schaums Outline is good one but a little lack of more theory any suggestions Which Book will do that...
Back
Top