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. paulmdrdo1

    MHB Solving the Time Needed for A & B to Complete a Job Alone

    1. A’s rate of doing work is three times that of B. On a given day A and B work together for 4 hours; then B is called away and A finishes the rest of the job in 2 hours. How long would it take B to do the complete job alone? if I let x = B's rate of work and 3x...
  2. S

    Can a preference relation be complete but not transitive?

    Homework Statement This is not a homework problem, but a topic in a microeconomics book that I am unclear about. My book argues that the set X = {a, b, c, d} of preferences can be (i) transitive but (ii) incomplete. Is it possible for a similar set of preferences to be (i) complete but (ii)...
  3. B

    Complete Removal of Matter from Space

    What is left if all matter and energy is removed from a particular region in space? For example, say I completely remove all of the matter and energy from a region of the air in front of me (also assuming no matter or energy moves in and out of this space once I do this), then what is left?
  4. B

    Orthonormality of a complete set of eigenvectors

    hello How to you rigorously express the orthonormality of a complete set of eigenvectors (|q\rangle)_q of the position operator given that these are necessarily generalized eigenvectors (elements of the distribution space of a rigged hilbert space)? The usual unformal condition \langle...
  5. U

    Complete absorption of E-fields by surface

    Homework Statement An EM wave is incident normally on a surface which absorbs all the electric field. Using maxwell equations, determine B-field on the other side. Homework Equations The Attempt at a Solution If all the E-field is absorbed, won't ET and Er = 0? Then none of...
  6. K

    Electronic book for complete beginner?

    Hey guys, I'm a complete beginner in electronics, and am looking for a beginner book to learn all about electronics. Can anyone give me some good reads?
  7. P

    MHB Using matrix to complete the square

    Given a quadratic form: x^2 - 4xy + 6xz + 2xt + 4y^2 + 2yz + 4yt + 5z^2 - 6zt - t^2, find the symmetric matrix that defines this, row reduce this matrix into row echelon form, and use this upper triangle matrix to complete the square and write the quadratic form as the sum/difference of...
  8. H

    Measurable with Respect to Complete Space

    Homework Statement Let f:(X,A,μ)->[0,infinity] have a Lebesgue integral, meaning that the inf(upper lebesgue sum)=sup(lower lebesgue sum)=L for a finite L. Show that f is measurable with respect to the completion of the sigma algebra A with respect to μ. You may fix an integrable set E...
  9. alyafey22

    MHB Complete spaces and Cauchy sequences

    I know that a metric space is complete if every Cauchy sequence converges that will surely designate compact metric spaces as complete spaces . I need to see examples of metric spaces which are not complete. Thanks in advance !
  10. I

    I think my program is complete What happen to this line? u(i)=sin(pi

    Homework Statement I think my program is complete.. What happen to this line? u(i)=sin(pi*x(i)); ?? Homework Equations n=10; c1=0; c2=0; k= 0.0025; L=1; h=0.1; alpha=1; T=0.025; n=L/h;m=T/k; lambda =alpha*k/(h^2); z=0:h:L...
  11. M

    Complete metric space can't have a countably infinite perfect space

    1. Homework Statement . Let ##(X,d)## be a complete metric space. Prove that if ##P \subset X## is perfect, then P is not countably infinite. 3. The Attempt at a Solution . Well, I couldn't think of a direct proof, I thought that in this case it may be easier to assume is countably infinite...
  12. M

    Every closed ball in X is complete, then X is complete

    Homework Statement . Prove that if every closed ball in a metric space X is a complete subspace, then X is complete. The attempt at a solution. Let ##\{x_n\}## be a cauchy sequence in X. Then, for ##ε=1##, ##\exists## ##n_0 \in \mathbb N##: ##\forall## ##m≥n_0##,##n≥n_0##...
  13. R

    Complete Random Design vs RCBD

    I want to understand the difference between Completely Randomized Design and Randomized Complete Block Design. Say for this example how we can categorize? An experiment is conducted to compare the starting salaries of male and female college graduates who find jobs. Pairs are formed by...
  14. A

    NP-Complete Problems: Definition, Classification & Examples

    As far as I understand NP-complete problems are problems that are NP and have some other problem that is reducible to itself. Basically it is a set of problems that are NP-complete and if one is solved all are solved, right? What is the point of defining such set of problems? Also there might...
  15. karush

    MHB Did I Correctly Complete the Tree Diagram?

    https://www.physicsforums.com/attachments/1163 well first want to see if i completed the tree diagram correctly text in the boxes are mine.
  16. M

    Is it possible to completely change your identity and start a new life?

    I've been watching a TV series recently called Person of Interest, it's really cool you should check it out. I'm curious though about people who somehow manage to completely wipe their identity and literally become a nobody and then acquire a new identity. I think legally the most thorough...
  17. Seydlitz

    Ordinary Induction vs Complete Induction

    With my current understanding, the ordinary principle of Mathematical Induction is a method to prove, whether some statement ##P(x)## is true for all ##x## in ##\mathbb{Z}##, considering the truth of ##P(1)## and then the truth of ##P(k+1)## assuming ##P(k)## is true. For Complete Induction...
  18. H

    Complete countable metric space

    Homework Statement It is clear that a countable complete metric space must have an isolated point,moreover,the set of isolated points is dense.what example is there of a countable complete metric space with points that are not isolated? Homework Equations The Attempt at a Solution
  19. F

    Power output of a solar panel if a complete row of cell is shadowed

    Homework Statement I have to analyse the power output of a solar panel using a basic electrical engineering circuit analysis of a solar module if a complete row of solar cells in it is shadowed (For example, such shading might be caused by dust that slides down the surface of inclined panels.)...
  20. A

    Electronics parts complete assortment

    Well I have no where else to look. I have tried various websites stores etc. I have looked into various sources sites extensively. And so far everything is just a source of aggravation. I can find all of the various parts but its over priced and takes to much searching to find parts. I just...
  21. I

    MHB Proving H is Complete & a Hilbert Space: Analysis of $\|.\|_H$

    Hi, Let H = \{(x_n)_n \subseteq \mathbb{R} | \sum_{n=1}^{\infty} x_n < \infty \} and for $(x_n)_n \in H$ define $$\|(x_n)_n\|_H = \sup_{n} \left|\sum_{k=0}^{n} x_k \right|$$ Prove that $H$ is complete. Is $H$ a Hilbert space? What is the best way to prove $H$ is complete? To prove it's a...
  22. M

    Let's see if anyone can complete this series

    2, 5, 14, 122, 365, ? The options are : a. 1029 b. 1094 c. 1059 d. 1000
  23. A

    MHB Arrange Numbers for Complete Squares Puzzle

    Arrange the numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 such that the summation of each two successive numbers is a complete square easy interesting question
  24. J

    How Do I Complete This Lewis Structure?

    Homework Statement Draw the best Lewis Dot Structures the following species: ClF4+Homework Equations none The Attempt at a Solution I calculated that there should be a total of 34 e- in the Lewis structure": 7 (1 chlorine atom) + 28 ( 7 from each of the four fluorine atoms) - 1(b/c the atom...
  25. alyafey22

    MHB He is a genius , he didn't complete school

    We might hear from one source or another that a famous scientist was always humiliated by his teacher when he was a student . We might hear about another who failed school or university but he became an inspiring figure after some years . So why do you think such things happen ? , is it because...
  26. M

    Complete set of stationary solutions

    In the infinite square well, the stationary states solutions form a complete set, and therefore I can write a function such as ( f(x) = -x^2 + x ) as an infinite sum of them, But this function is, clearly, not a solution of S.E., although it's written as a sum of solutions. Why is it not a...
  27. fluidistic

    Show that a vector space is not complete (therefore not a Hilbert spac

    Homework Statement Consider the space of continuous functions in [0,1] (that is C([0,1]) over the complex numbers with the following scalar product: ##\langle f , g \rangle = \int _0 ^1 \overline{f(x)}g(x)dx##. Show that this space is not complete and therefore is not a Hilbert space. Hint:Find...
  28. Roodles01

    Is a wave function as complete as can be

    For a wave function describing the state of an isolated system in 1D, does a wave function describe a system completely?
  29. O

    Math books for a complete beginner

    Hi, I'm a high school student from Brazil who knows very little math, but I want to learn more (I've learned some stuff in school and forgot almost all of it).* Which books would you recommend? I've heard of Courant's What is Mathematics and of the Schaum's Outlines series. Are these...
  30. A

    MHB What is the simplest method for solving polynomial equations?

    In your opinion what is the best way to introduce completing the square, in fact I do not like the way sub and add the squared half of x coefficient, after making x^2 coefficient 1 saying it is complicated... Thanks
  31. S

    Write the complete solution as the particular solution plus any multip

    Homework Statement Could someone please help me do this problem?: “Write the complete solution as x_p plus any multiple of s in the nullspace: x + 3y + 3z = 1 2x + 6y + 9z = 5 –x – 3y + 3z = 5” The answer is x = x_p + x_n = {{-2},{0},{1}} + x_2 {{-3, 1, 0}}. Homework Equations Ax...
  32. J

    Need a complete list of functions and thier inverses

    I can't find this anywhere on google. I'm looking for a complete list of functions and their inverses. Here's a partial list as an example *, / +, - e^x, ln(x) sin(), sin^-1() d/dx, ∫ etc.. Why isn't there a list of all of them? You would think that some mathematician would find joy in...
  33. P

    Complete solution of the ΛCDM model problems

    Introduction: A new cosmology based on the production of massless particles (in the early de Sitter phase) and ΛCDM particles (in the transition to a late time de Sitter stage) has been discussed. The same mechanism avoids the initial singularity, particle horizon and the late time coincidence...
  34. samalkhaiat

    Windows was unable to complete the format

    "windows was unable to complete the format" Like myself, my PC is getting old! I have just noticed that it is not able to format any CD's and most DVD's. It certainly can not format any disk which has been erased. After 20 minutes of trying, it displays the message "windows was unable to...
  35. H

    Bohmian mechanics as 'complete' theory

    Hello, forum! I am puzzling my way through some interpretation. In the famous EPR paper, the authors ask whether quantum mechanics is a 'complete' theory in the sense of whether or not the wave function completely describes the physical circumstances in question. EPR conclude that it is not...
  36. S

    Munkres Topology - Chapter 7 - Complete Metric Spaces and Function Spaces

    Hello, I was wondering if it was possible (or advisable) to read Chapter 7 of Munkres (Complete Metric Spaces and Function Spaces) without having done Tietze Extension Theorem, the Imbeddings of Manifolds section, the entirety of Chapter 5 (Tychonoff Theorem) and the entirety of Chapter 6...
  37. M

    Can you reach absolute zero in complete empty space

    Ok, so I know that the laws of physics say reaching absolute zero temperature is impossible, but suppose we took a box that was perfectly insulated in completely empy space, and I took all the particles out of it to create a vacuum. Now, since there are no particles in the box, then wouldn't...
  38. STEMucator

    Complete the square ( Potentially )?

    Homework Statement There was a question on my exam a few days ago. Using Lagrange to find the max/min on a region. We only had to answer a certain amount of questions and I never got to this one. I'm working on it now though out of curiosity. R = { (x,y) | x2 + xy + y2 ≤ 3 } f(x,y) =...
  39. K

    Is the Relation R Complete Given Asymmetry in P?

    Homework Statement Assume a relation P that is asymmetric on a set X that is not empty. Define the binary relation R on X by xRy iff y P x is false. Prove that R is complete Homework Equations Asymmetry: xRy \rightarrow \neg (yRx) Now, I think I got a proof, but I am not sure...
  40. F

    How many exercises do I have to complete ?

    I'm taking PoMA-Rudin, do I have to complete all the exercises after every chapter to be regarded as understanding the material ? Does all the tools for solving the exercises lie in the material? Because I feel many problems require more than the textbook. Thanks.
  41. O

    Working out how many complete waves are sent out.

    Homework Statement A source of light emits a train of waves lasting 0.04 μs. The light has a wavelength of 600nm and the speed of light is 3×108ms-1. How many complete waves are sent out? a)2.0×107 b)4.5×107 c)2.0×1010 d)4.5×1013 Homework Equations f=v/wavelength (sorry, I couldn't...
  42. V

    Complete sets and eigenvalues question

    Let's say I'm looking at the infinite square well. Typically, given some arbitrary initial (normalized) wavefunction, we can decompose it into a linear combination of components of the complete set (on the interval [-a,a] or whatever) of sin's and cos's. Then, if you measure something like the...
  43. A

    Family of continuous functions defined on complete metric spaces

    Homework Statement Let X and Y be metric spaces such that X is complete. Show that if {fα(x) : α ∈ A} is a bounded subset of Y for each x ∈ X, then there exists a nonempty open subset U of X such that {fα(x) : α ∈ A, x ∈ U} is a bounded subset of Y. Homework Equations Definition of...
  44. D

    How Does the Riemann Integral Affect Lp Space Completeness?

    "All Lp spaces, (except where p=∞) fail to be complete under the Reimann integral"? I am trying to learn about the Lebesgue integral and Lebesgue measurability. None of my textbooks really cover it from the basics, but I found this document online which seems to be pretty through in...
  45. C

    Solving 2.52 Elevator Problem how to calculate time of a complete trip?

    Homework Statement Hi everyone, I am just wondering how you would solve this question.. 2. Elevator Problem (Practice on Segmented Motion) A hotel elevator ascends 200 m with maximum speed of 5 m/s. Its acceleration and deceleration both have a magnitude of 1.0 m/s How long does...
  46. F

    Is the list of particles complete and unique?

    I'm wondering if the list of particles in the SM is both complete and unique? Or could we find other particles and interactions that could also be included in the SM? Phyisicists sometimes invent fields and particles to account for Dark matter and inflation, etc. But that introduces particles...
  47. Drakkith

    Move to Tucson Completed: New Astronomy Adventures Ahead!

    Well, my move to Tucson is completed! 1100 miles, 20 hours, most of which was across Texas! (Shreveport, LA to Tucson, AZ) Glad to be out here in Tucson finally. Already sent in my application to join the local astronomy organization, and I can't wait to go to some of the observatories around...
  48. M

    Complete list of mathematical notations

    hello! is there a complete list of mathematical notations? thanks!
  49. M

    Most complete book/journal/database/electronic-material databases

    hello! can you post your bookmarks about: - book repositories - journal repositories - database repositories - electronic material repositories etc for example, when you are looking for all possible books about a specific subject, you just search at amazon? or what else? thanks!
  50. T

    Is this a complete test to show that a matrix is orthogonal?

    I used to test orthogonality by using the definition MT = M-1, which means I always calculated the inverse of the matrices. However, isn't it true that if M is orthogonal, then MMT = I? If we multiply both side by M-1, we get MT = M-1. Can I use this to proof the orthogonality of a matrix...
Back
Top