Content deleted Content added
→Table or list?: new section |
|||
Line 372:
[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 15:57, 19 November 2009 (UTC)
The table looks better, but perhaps we could have fewer columns:
{| class="wikitable"
|-
! Complexity class
! Type of problem
! Model of computation
! Resource constraint
|-
| [[DTIME]](''f''(''n''))
| Decision problem
| Deterministic Turing machine
| Time ''f''(''n'')
|-
| [[P (complexity)|P]]
| Decision problem
| Deterministic Turing machine
| Polynomial time
|-
| [[EXPTIME]]
| Decision problem
| Deterministic Turing machine
| Exponential time
|-
| [[NTIME]](''f''(''n''))
| Decision problem
| Non-deterministic Turing machine
| Time ''f''(''n'')
|-
| [[NP (complexity)|NP]]
| Decision problem
| Non-deterministic Turing machine
| Polynomial time
|-
| [[NEXPTIME]]
| Decision problem
| Non-deterministic Turing machine
| Exponential time
|-
|}
— [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 13:33, 21 November 2009 (UTC)
| |||