Cobham's thesis
id:
cobham-s-thesis-194-8170126
title:
Cobham's thesis
text:
Cobham's thesis, also known as Cobham–Edmonds thesis, asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. In modern terms, it identifies tractable problems with the complexity class P. Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solut
brand slug:
wiki
category slug:
encyclopedia
description:
Thesis which states computational problems can only be feasibly computed in polynomial time
original url:
https://en.wikipedia.org/wiki/Cobham%27s_thesis
date created:
date modified:
2023-11-20T13:15:48Z
main entity:
{"identifier":"Q5138877","url":"https://www.wikidata.org/entity/Q5138877"}
image:
fields total:
13
integrity:
14