Content deleted Content added
→Table or list?: new section |
|||
Line 307:
::Yes, sure. I'm not a fan of that myself. The whole section on intractability is a bit sketchy, but I'm not too sure how to present it properly. It feels like a "criticisms of complexity theory" section, but presented badly. There might be interesting things to mention in such a section, like the fact that SAT solvers in reality to do handle largish instances (10000+ variables) in practice, and that even though problems might be hard to solve exactly, they might be easy to approximate. I'll see if I can get more information on this and write some stuff up. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 23:56, 3 November 2009 (UTC)
== Table or list? ==
Which one of the following seems better for presenting information?
{| class="wikitable"
|-
! Complexity class
! Type of problem
! Model of computation
! Bounded resource
! Bound for the resource
|-
| [[DTIME]](''f''(''n''))
| Decision problem
| Deterministic Turing machine
| Time
| ''f''(''n'')
|-
| [[P (complexity)|P]]
| Decision problem
| Deterministic Turing machine
| Time
| polynomial
|-
| [[EXPTIME]]
| Decision problem
| Deterministic Turing machine
| Time
| exponential
|-
| [[NTIME]](''f''(''n''))
| Decision problem
| Non-deterministic Turing machine
| Time
| ''f''(''n'')
|-
| [[NP (complexity)|NP]]
| Decision problem
| Non-deterministic Turing machine
| Time
| polynomial
|-
| [[NEXPTIME]]
| Decision problem
| Non-deterministic Turing machine
| Time
| exponential
|-
|}
OR a list, like this:
* [[DTIME]](f(n)): Decision problems solvable by a deterministic Turing machine within time ''f''(''n'').
* [[P (complexity)|P]]: Decision problems solvable by a deterministic Turing machine within time polynomial in the input size.
* [[EXPTIME]]: Decision problems solvable by a deterministic Turing machine within time exponential in the input size.
* [[NTIME]](f(n)): Decision problems solvable by a nondeterministic Turing machine within time ''f''(''n'').
* [[NP (complexity)|NP]]: Decision problems solvable by a nondeterministic Turing machine within time polynomial in the input size.
* [[NEXPTIME]]: Decision problems solvable by a nondeterministic Turing machine within time exponential in the input size.
[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 15:57, 19 November 2009 (UTC)
| |||