Timeline for The defining property of problems in NP [duplicate]
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2020 at 10:30 | history | edited | CommunityBot |
Commonmark migration
|
|
| Apr 20, 2017 at 23:28 | history | duplicates list edited | D.W.♦ | duplicates list edited from What is the definition of P, NP, NP-complete and NP-hard? to What is the definition of P, NP, NP-complete and NP-hard?, What is the difference between an algorithm, a language and a problem? | |
| Apr 20, 2017 at 23:28 | history | closed | D.W.♦ | Duplicate of What is the definition of P, NP, NP-complete and NP-hard? | |
| Apr 20, 2017 at 23:28 | comment | added | D.W.♦ | Since you said you want a standard definition, your question seems to be answered by our reference questions on the topic, namely, cs.stackexchange.com/q/9556/755 and cs.stackexchange.com/q/13669/755. The former gives the intuition and the latter shows how to formalize it using set theory, by talking about languages. This topic is also well covered in standard textbooks and on Wikipedia (en.wikipedia.org/wiki/P_%28complexity%29, en.wikipedia.org/wiki/NP_%28complexity%29). There's little point in us repeating material already available in standard sources. | |
| Apr 20, 2017 at 23:24 | comment | added | D.W.♦ | We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher | |
| Apr 20, 2017 at 2:47 | comment | added | StudentsTea | @6005 - Feel free to provide the standard definition using notation from Set Theory--as that's what the post is asking for in an answer. | |
| Apr 20, 2017 at 2:19 | comment | added | Caleb Stanford |
I really need to see a formal definition of the proposition used to build that class--as well as a formal definition of the universe of objects we're starting with. It is good to have a formal definition, and the usual one is quite formal. The rest of your post, however, uses nonstandard terminology and is honestly confusing, as well as far from formal. Rather than try to interpret things in your own terms using words like "universe of discourse", I would suggest you learn how to formalize the standard terms and concepts.
|
|
| Apr 20, 2017 at 2:16 | comment | added | Caleb Stanford |
In spite of Russell's Paradox It has nothing to do with Russel's paradox; these are sets of binary strings, there is no membership or self-reference in what you call the "universe of discourse". Another thing: we use all-caps ($\text{P}$ and $\text{NP}$) for complexity classes. Blackboard bold is usually reserved for canonical sets (with some exceptions).
|
|
| Apr 20, 2017 at 1:54 | history | edited | StudentsTea | CC BY-SA 3.0 |
Somehow lost all the hyperlinks along the way. Put them back in.
|
| Apr 20, 2017 at 1:23 | comment | added | mhum | If you are interested in logical characterizations of NP, it may be worthwhile to investigate Fagin's Theorem. | |
| Apr 20, 2017 at 0:59 | history | asked | StudentsTea | CC BY-SA 3.0 |