Quizzes for review
Informally, a problem is in the class NPC—and we refer to it as being NP-complete—if it is in NP and is as hard
as any problem in NP. We shall formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we will state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to proving NP-complete problems intractable—without a conclusive outcome—we cannot rule out the possibility that the NP-complete problems are in fact solvable in polynomial time.
English - English
- Users who have edit permission for words - All Users
- Screen new word creation
- Screen word edits
- Screen word deletion
- Screen the creation of new headword that may be duplicates
- Screen changing entry name
- Users authorized to vote on judging - Editor
- Number of votes required for decision - 1
- Users who have edit permission for sentences - All Users
- Screen sentence deletion
- Users authorized to vote on judging - Editor
- Number of votes required for decision - 1
- Users who have edit permission for quizzes - All Users
- Users authorized to vote on judging - Editor
- Number of votes required for decision - 1
