33:
507:, it is usually implicitly assumed that any string in {0, 1} represents an instance of the computational problem in question. However, sometimes not all strings {0, 1} represent valid instances, and one specifies a proper subset of {0, 1} as the set of "valid instances". Computational problems of this type are called
302:, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.
469:"Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city."
62:
738:
771:
747:
711:
151:
for every instance/case. The question then is, whether there exists an algorithm that maps instances to solutions. For example, in the
84:
194:
that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with various
766:
504:
183:
175:
174:
One is often interested not only in mere existence of an algorithm, but also how efficient the algorithm can be. The field of
523:
419:
asks for finding a "best possible" solution among the set of all possible solutions to a search problem. One example is the
215:, problems that consume polynomial time for probabilistic classical machines (e.g. computers with random number generators)
349:
352:
asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is
486:
256:
is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is
101:
45:
461:
55:
49:
41:
703:
630:
478:
538:
Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.
599:
228:
66:
607:
239:. This is important since the complexity is expressed as a function of the length of the input representation.
179:
674:; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography",
595:
306:
132:
625:
416:
482:
187:
650:
278:
A decision problem is typically represented as the set of all instances for which the answer is
171:. Computational problems are one of the main objects of study in theoretical computer science.
743:
707:
619:
258:
152:
136:
683:
603:
456:
448:
253:
211:
195:
191:
508:
498:
232:
168:
439:
Optimization problems are represented by their objective function and their constraints.
729:
721:
695:
452:
299:
203:
687:
760:
725:
236:
17:
733:
671:
667:
541:
Decision promise problems are usually represented as pairs of disjoint subsets (
459:, that is, it isn't just "yes" or "no". One of the most famous examples is the
455:) is expected for every input, but the output is more complex than that of a
207:, problems that consume polynomial time for deterministic classical machines
109:
223:, problems that consume polynomial time for probabilistic quantum machines.
182:) solving a given problem will require, and explain why some problems are
282:. For example, primality testing can be represented as the infinite set
131:
is a computational problem that has a solution, as there are many known
474:
167:. An example of a computational problem without a solution is the
178:
addresses such questions by determining the amount of resources (
372:
from {0, 1} to the nonnegative integers. For a search relation
320:= {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}
219:
26:
514:
The following is an example of a (decision) promise problem:
622:, alternative approaches to solving problems computationally
594:
Promise problems play an important role in several areas of
313:. For example, factoring can be represented as the relation
309:
consisting of all the instance-solution pairs, called a
227:
Both instances and solutions are represented by binary
135:
algorithms. A computational problem can be viewed as a
368:
A counting problem can be represented by a function
700:Computational Complexity: A Conceptual Perspective
360:, count the number of nontrivial prime factors of
742:, Princeton University Press, pp. 575–604,
235:are usually represented as binary strings using
54:but its sources remain unclear because it lacks
108:is one that asks for a solution in terms of an
555:) of {0, 1}. The valid instances are those in
728:(2008), "IV.20 Computational Complexity", in
8:
534:has an independent set of size at least 10."
190:. Solvable computational problems belong to
231:, namely elements of {0, 1}. For example,
163:that are the nontrivial prime factors of
97:Problem a computer might be able to solve
85:Learn how and when to remove this message
583:represent the instances whose answer is
147:together with a, possibly empty, set of
642:
324:which consist of all pairs of numbers (
739:The Princeton Companion to Mathematics
198:. For example, the complexity classes
376:, the counting problem associated to
305:A search problem is represented as a
7:
123:, find a nontrivial prime factor of
159:, and solutions are prime numbers
25:
155:, the instances are the integers
31:
505:computational complexity theory
176:computational complexity theory
112:. For example, the problem of
1:
688:10.1016/S0019-9958(84)80056-X
431:, find an independent set of
772:Theoretical computer science
487:theoretical computer science
102:theoretical computer science
788:
704:Cambridge University Press
631:Transcomputational problem
496:
479:combinatorial optimization
356:"Given a positive integer
266:"Given a positive integer
119:"Given a positive integer
608:interactive proof systems
600:hardness of approximation
596:computational complexity
180:computational complexity
40:This article includes a
676:Information and Control
530:has size at most 5, or
421:maximum independent set
289:= {2, 3, 5, 7, 11, ...}
69:more precise citations.
767:Computational problems
732:; Barrow-Green, June;
451:a single output (of a
653:for the notation used
522:, determine if every
336:is a prime factor of
133:integer factorization
106:computational problem
626:Model of computation
417:optimization problem
411:Optimization problem
651:regular expressions
483:operations research
18:Computation problem
591:, respectively.
462:traveling salesman
192:complexity classes
42:list of references
749:978-0-691-11880-2
713:978-0-521-88473-0
620:Lateral computing
435:of maximum size."
259:primality testing
196:abstract machines
153:factoring problem
95:
94:
87:
16:(Redirected from
779:
752:
716:
690:
654:
647:
604:property testing
509:promise problems
457:decision problem
449:function problem
443:Function problem
380:is the function
350:counting problem
344:Counting problem
254:decision problem
248:Decision problem
90:
83:
79:
76:
70:
65:this article by
56:inline citations
35:
34:
27:
21:
787:
786:
782:
781:
780:
778:
777:
776:
757:
756:
750:
730:Gowers, Timothy
722:Goldreich, Oded
720:
714:
696:Goldreich, Oded
694:
672:Selman, Alan L.
666:
663:
658:
657:
648:
644:
639:
616:
582:
575:
568:
561:
554:
547:
524:independent set
518:"Given a graph
501:
499:Promise problem
495:
493:Promise problem
481:, important in
445:
427:"Given a graph
413:
388:
346:
311:search relation
296:
270:, determine if
250:
245:
237:binary encoding
233:natural numbers
169:Halting problem
98:
91:
80:
74:
71:
60:
46:related reading
36:
32:
23:
22:
15:
12:
11:
5:
785:
783:
775:
774:
769:
759:
758:
755:
754:
748:
726:Wigderson, Avi
718:
712:
692:
682:(2): 159–173,
662:
659:
656:
655:
641:
640:
638:
635:
634:
633:
628:
623:
615:
612:
580:
573:
566:
559:
552:
545:
536:
535:
497:Main article:
494:
491:
471:
470:
453:total function
444:
441:
437:
436:
412:
409:
408:
407:
386:
366:
365:
345:
342:
322:
321:
300:search problem
295:
294:Search problem
292:
291:
290:
276:
275:
249:
246:
244:
241:
225:
224:
216:
208:
129:
128:
96:
93:
92:
50:external links
39:
37:
30:
24:
14:
13:
10:
9:
6:
4:
3:
2:
784:
773:
770:
768:
765:
764:
762:
751:
745:
741:
740:
735:
731:
727:
723:
719:
715:
709:
705:
701:
697:
693:
689:
685:
681:
677:
673:
669:
665:
664:
660:
652:
646:
643:
636:
632:
629:
627:
624:
621:
618:
617:
613:
611:
609:
605:
601:
597:
592:
590:
586:
579:
572:
565:
558:
551:
544:
539:
533:
529:
525:
521:
517:
516:
515:
512:
510:
506:
500:
492:
490:
488:
484:
480:
476:
468:
467:
466:
464:
463:
458:
454:
450:
442:
440:
434:
430:
426:
425:
424:
422:
418:
410:
405:
401:
397:
393:
389:
383:
382:
381:
379:
375:
371:
363:
359:
355:
354:
353:
351:
343:
341:
339:
335:
331:
327:
319:
316:
315:
314:
312:
308:
303:
301:
293:
288:
285:
284:
283:
281:
273:
269:
265:
264:
263:
261:
260:
255:
247:
242:
240:
238:
234:
230:
222:
221:
217:
214:
213:
209:
206:
205:
201:
200:
199:
197:
193:
189:
185:
181:
177:
172:
170:
166:
162:
158:
154:
150:
146:
142:
138:
134:
126:
122:
118:
117:
116:
115:
111:
107:
103:
89:
86:
78:
68:
64:
58:
57:
51:
47:
43:
38:
29:
28:
19:
737:
734:Leader, Imre
699:
679:
675:
668:Even, Shimon
645:
598:, including
593:
588:
584:
577:
570:
563:
556:
549:
542:
540:
537:
531:
527:
519:
513:
502:
472:
460:
446:
438:
432:
428:
420:
414:
403:
399:
395:
391:
384:
377:
373:
369:
367:
361:
357:
347:
337:
333:
329:
325:
323:
317:
310:
304:
297:
286:
279:
277:
271:
267:
257:
251:
226:
218:
210:
202:
173:
164:
160:
156:
148:
144:
140:
130:
124:
120:
113:
105:
99:
81:
75:October 2015
72:
61:Please help
53:
477:problem in
188:undecidable
184:intractable
67:introducing
761:Categories
661:References
274:is prime."
473:It is an
465:problem:
423:problem:
332:), where
149:solutions
141:instances
114:factoring
110:algorithm
736:(eds.),
698:(2008),
614:See also
390:(x) = |{
307:relation
475:NP-hard
229:strings
63:improve
746:
710:
606:, and
637:Notes
447:In a
406:) }|.
298:In a
243:Types
145:cases
48:, or
744:ISBN
708:ISBN
649:See
587:and
576:and
485:and
104:, a
684:doi
585:yes
574:yes
560:yes
546:yes
526:in
503:In
415:An
280:yes
220:BQP
212:BPP
186:or
143:or
139:of
137:set
100:In
763::
724:;
706:,
702:,
680:61
678:,
670:;
610:.
602:,
589:no
581:no
569:.
567:no
562:∪
553:no
548:,
511:.
489:.
402:,
394::
364:."
348:A
340:.
328:,
262::
252:A
127:."
52:,
44:,
753:.
717:.
691:.
686::
578:L
571:L
564:L
557:L
550:L
543:L
532:G
528:G
520:G
433:G
429:G
404:y
400:x
398:(
396:R
392:y
387:R
385:f
378:R
374:R
370:f
362:n
358:n
338:n
334:p
330:p
326:n
318:R
287:L
272:n
268:n
204:P
165:n
161:p
157:n
125:n
121:n
88:)
82:(
77:)
73:(
59:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.