Content deleted Content added
→Table or list?: agree |
|||
Line 422:
:Alright, agreed. Maybe if we end up listing only decision problems, that column can be taken out too. --[[User:RobinK|Robin]] ([[User talk:RobinK|talk]]) 14:33, 21 November 2009 (UTC)
By the way, while "polynomial time" is fairly obvious, "exponential time" isn't. If someone new to the topic had to guess what it means, it might be easy to think something like [[E (complexity)]] instead of something like [[EXPTIME]]. To add to the confusion, we have a (somewhat strange) article [[Exponential time]] that strengthens the false impression. Hence we might consider something more explicit like this:
{| 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
| Time poly(''n''), i.e. polynomial
|-
| [[EXPTIME]]
| Decision problem
| Deterministic Turing machine
| Time 2<sup>poly(''n'')</sup>, i.e. exponential
|-
|}
— [[User:Miym|Miym]] ([[User talk:Miym|talk]]) 15:30, 21 November 2009 (UTC)
| |||