Talk:Computational complexity theory: Difference between revisions

Revision as of 06:25, 31 July 2007

Revision as of 11:49, 31 July 2007

Line 37:

I wonder where would be a good place to mention that we know some problems not in '''P''', for instance [[:Presburger arithmetic|Presburger arithmetic]]. --AxelBoldt

I've added it to [[:Complexity classes P=NP and NPproblem|Complexity classes P and NP]]. It should also be added to [[:EXPTIME|EXPTIME]], whenever someone gets around to writing it. I would put it under [[P (complexity)|P]] too, except that's more of a redirect than a real article. --[[user:LC|LC]]

----

Line 124:

:I've added a [[run-time analysis]] article. [[User:Groupthink|Groupthink]] 21:02, 28 June 2007 (UTC)

:I disagree. There is already a [[Complexity classes P=NP and NPproblem|P/NP]] page elsewhere. And the majority of complexity theory deals with run-time complexity. P/NP is only included here because of its fundamental importance in complexity theory and computer science in general. If anything, the P/NP could be toned down, and the reader directed to the other page. But thanks for working on this. It could really help from your input. [[User:Scottcraig|Scottcraig]] 17:13, 30 June 2007 (UTC)

::Then perhaps [[computational complexity theory]] should be merged into [[run-time analysis]], and the material on boolean decidability and P/NP-completeness in comp. complexity should be merged into [[Boolean satisfiability problem]] and [[P=NP problem|Complexity classes P and NP]] respectively? [[User:Groupthink|Groupthink]] 21:42, 30 June 2007 (UTC)

== Asymptotic complexity ==