User:HusseinHoudrouge/sandbox
Complexity class / From Wikipedia, the free encyclopedia
In computational complexity theory, a problem is NP-complete if it is in NP, and it is NP-hard. Informally, a problem is in NP if there exist an efficient algorithm, a polynomial time algorithm, that can verify the solution to this problem. It is NP-hard if every problem in NP can be reduced to it in polynomial time. In other, NP-hard problem is at least as hard as the hardest problem in NP. A problem that is NP-Hard does not necessary belongs to NP.
This is the user sandbox of HusseinHoudrouge. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review! |
This user page is actively undergoing a major edit for a little while. To help avoid edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 13:22, 9 January 2022 (UTC) (2 years ago) ā this estimate is cached, update. Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions. |
This article may be confusing or unclear to readers. (July 2012) |
The name "NP-complete" is abbreviation for "Nondeterministic Polynomial-time Complete". In this name, "Nondeterministic Polynomial-time" refers to the complexity class of Decision problems that can be decided in polynomial number of steps using nondeterministic Turing machines, a Turing machine that have an nondeterministic transition function. "Complete" refers to the property of being able to simulate every problem in a given complexity class.
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 "efficiently", there is no known algorithm till now that decides NP-Complete problems efficiently. That is, the Time complexity required to decide the problem by any currently known algorithm, so far, increases rapidly as the size of the problem grows.
Knowing if an efficient algorithm exists to decide NP-Complete problem is a major unsolved problems in computer science, called the P versus NP problem. Since NP-complete problems are very common and frequent in several fields, several coping mechanism and algorithm techniques has been developed such the using heuristic methods, approximation algorithms, and Fixed-parameter algorithms.