561
个编辑
更改
无编辑摘要
A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice ''any'' solution takes too many resources to be useful, is known as an '''{{visible anchor|intractable problem}}'''.<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> Conversely, a problem that can be solved in practice is called a '''{{visible anchor|tractable problem}}''', literally "a problem that can be handled". The term ''[[wikt:infeasible|infeasible]]'' (literally "cannot be done") is sometimes used interchangeably with ''[[wikt:intractable|intractable]]'',<ref>{{cite book |title=Algorithms and Complexity |first=Gerard |last=Meurant |year=2014 |isbn=978-0-08093391-7 |page=[https://books.google.com/books?id=6WriBQAAQBAJ&pg=PA4&dq=computational+feasibility+tractability p. 4]}}</ref> though this risks confusion with a [[feasible solution]] in [[mathematical optimization]].<ref>
在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft，J.e.，Motwani，R.和Ullman，J.D.（2007）[[自动机理论导论，语言，而计算]]，Addison-Wesley，Boston/San-Francisco/newyork（第368页）</ref>相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。
在理论上可以解决的问题（例如，给定大量但有限的资源，特别是时间），但实际上“任何”解决方案都需要太多的资源来解决，因此被称为“{可见锚|棘手问题}”。<ref>Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) [[Introduction to Automata Theory, Languages, and Computation]], Addison Wesley, Boston/San Francisco/New York (page 368)</ref> 相反，一个可以在实践中解决的问题称为“{{visible anchor | tractible problem}}”，字面意思是“可以处理的问题”。术语''[[wikt：不可行|不可行]]''（字面意思是“不能做”）有时与“[[难对付的|棘手]]”互换使用，尽管这有可能与[[数学优化]]中的[[可行解]]混淆。
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.
Before the actual research explicitly devoted to the complexity of algorithmic problems started off, numerous foundations were laid out by various researchers. Most influential among these was the definition of Turing machines by Alan Turing in 1936, which turned out to be a very robust and flexible simplification of a computer.