466:
bits. At the same time, the number of arithmetic operations cannot be bounded by the number of integers in the input (which is constant in this case, there are always only two integers in the input). Due to the latter observation, the algorithm does not run in strongly polynomial time. Its real
154:
However, if an algorithm runs in polynomial time in the arithmetic model, and in addition, the binary length of all inputs, outputs, and intermediate values is polynomial in the number of input values, then it is always polynomial-time in the Turing model. Such an algorithm is said to run in
323:
However, for the first condition, there are algorithms that run in a number of Turing machine steps bounded by a polynomial in the length of binary-encoded input, but do not take a number of arithmetic operations bounded by a polynomial in the number of input numbers. The
320:, and thus exponential rather than polynomial in the space used to represent the input. Hence, it is not possible to carry out this computation in polynomial time on a Turing machine, but it is possible to compute it by polynomially many arithmetic operations.
171:. In this model of computation the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform, regardless of the sizes of the operands. The algorithm runs in strongly polynomial time if:
92:
In the arithmetic model, every basic arithmetic operation on real numbers (addition, subtraction, multiplication and division) can be done in a single step, whereas in the Turing model the run-time of each arithmetic operation depends on the length of the
37:
is – generally speaking – an algorithm whose running time is upper-bounded by some polynomial function of the input size. The definition naturally depends on the computational model, which determines how the
182:
Any algorithm with these two properties can be converted to a polynomial time algorithm by replacing the arithmetic operations by suitable algorithms for performing the arithmetic operations on a
89:
In the arithmetic model, every real number requires a single memory cell, whereas in the Turing model the storage size of a real number depends on the number of bits required to represent it.
150:
runs in polynomial time in the
Arithmetic model, but not in the Turing model. This is because the number of bits required to represent the outcome is exponential in the input size.
464:
417:
291:
249:
144:
65:
The difference between strongly- and weakly-polynomial time is when the inputs to the algorithms consist of integer or rational numbers. It is particularly common in
318:
211:
509:
489:
370:
350:
518:. A well-known example of a problem for which a weakly polynomial-time algorithm is known, but is not known to admit a strongly polynomial-time algorithm, is
175:
the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
615:
538:
In order to specify the arithmetic model, there are several ways to define the division operation. The outcome of dividing an integer
650:
168:
82:
51:
672:
553:
The rational number a/b, except if it is known in advance that a/b is an integer, in which case it is the integer a/b.
66:
33:
329:
523:
589:
550:
The rational number a/b (i.e., not reduced, since reduction cannot be done in strongly-polynomial time).
422:
375:
638:
593:
585:
325:
102:
519:
514:
An algorithm that runs in polynomial time but that is not strongly polynomial is said to run in
262:
220:
115:
646:
611:
597:
256:
147:
603:
28:
625:
296:
189:
97:
Some algorithms run in polynomial time in one model but not in the other one. For example:
621:
556:
The rational number a/b, except if a/b is an integer, in which case it is the integer a/b.
563:
In all versions, strongly-polynomial-time implies polynomial-time in the Turing model.
494:
474:
355:
335:
183:
78:
47:
666:
602:, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin,
178:
the space used by the algorithm is bounded by a polynomial in the size of the input.
17:
530:
of values in the problem instead of the lengths and is not truly polynomial time.
607:
105:
runs in polynomial time in the Turing model, but not in the arithmetic model.
186:. The second condition is strictly necessary: given the integer
511:
in bits and not only on the number of integers in the input.
217:
in the Turing machine model), it is possible to compute
46:
is measured. Two prominent computational models are the
641:(2003). "Preliminaries on algorithms and Complexity".
522:. Weakly polynomial time should not be confused with
497:
477:
425:
378:
358:
338:
299:
265:
223:
192:
118:
643:
599:
Geometric algorithms and combinatorial optimization
332:of two integers is one example. Given two integers
503:
483:
458:
411:
364:
344:
312:
285:
243:
205:
138:
62:is polynomial only in the Turing machine model.
419:arithmetic operations on numbers with at most
8:
167:Strongly polynomial time is defined in the
496:
476:
424:
377:
357:
337:
304:
298:
275:
270:
264:
233:
228:
222:
197:
191:
128:
123:
117:
77:Two common computational models are the
58:is polynomial in both models, whereas a
572:
259:. However, the space used to represent
213:(which takes up space proportional to
7:
580:
578:
576:
56:strongly-polynomial time algorithm
25:
459:{\displaystyle O(\log a+\log b)}
412:{\displaystyle O(\log a+\log b)}
60:weakly-polynomial time algorithm
169:arithmetic model of computation
453:
429:
406:
382:
1:
467:running time depends on the
689:
112:numbers and then computes
645:. Vol. 1. Springer.
608:10.1007/978-3-642-78240-4
372:, the algorithm performs
286:{\displaystyle 2^{2^{n}}}
244:{\displaystyle 2^{2^{n}}}
139:{\displaystyle 2^{2^{n}}}
108:The algorithm that reads
42:is measured, and how the
34:polynomial-time algorithm
157:strongly polynomial time
559:The integer floor(a/b).
526:, which depends on the
330:greatest common divisor
524:pseudo-polynomial time
516:weakly polynomial time
505:
485:
460:
413:
366:
346:
314:
287:
255:multiplications using
245:
207:
140:
506:
486:
461:
414:
367:
347:
315:
313:{\displaystyle 2^{n}}
288:
246:
208:
206:{\displaystyle 2^{n}}
141:
639:Schrijver, Alexander
594:Schrijver, Alexander
495:
475:
423:
376:
356:
336:
297:
263:
221:
190:
116:
73:Computational models
542:by another integer
326:Euclidean algorithm
293:is proportional to
103:Euclidean algorithm
18:Strongly polynomial
673:Complexity classes
520:linear programming
501:
481:
456:
409:
362:
342:
328:for computing the
310:
283:
241:
203:
136:
617:978-3-642-78242-8
586:Grötschel, Martin
546:could be one of:
504:{\displaystyle b}
484:{\displaystyle a}
365:{\displaystyle b}
345:{\displaystyle a}
257:repeated squaring
148:repeated squaring
16:(Redirected from
680:
657:
656:
635:
629:
628:
582:
510:
508:
507:
502:
490:
488:
487:
482:
465:
463:
462:
457:
418:
416:
415:
410:
371:
369:
368:
363:
351:
349:
348:
343:
319:
317:
316:
311:
309:
308:
292:
290:
289:
284:
282:
281:
280:
279:
250:
248:
247:
242:
240:
239:
238:
237:
212:
210:
209:
204:
202:
201:
145:
143:
142:
137:
135:
134:
133:
132:
83:arithmetic model
52:arithmetic model
29:computer science
21:
688:
687:
683:
682:
681:
679:
678:
677:
663:
662:
661:
660:
653:
637:
636:
632:
618:
584:
583:
574:
569:
536:
493:
492:
473:
472:
421:
420:
374:
373:
354:
353:
334:
333:
300:
295:
294:
271:
266:
261:
260:
229:
224:
219:
218:
193:
188:
187:
165:
124:
119:
114:
113:
75:
23:
22:
15:
12:
11:
5:
686:
684:
676:
675:
665:
664:
659:
658:
651:
630:
616:
590:Lovász, László
571:
570:
568:
565:
561:
560:
557:
554:
551:
535:
532:
500:
480:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
361:
341:
307:
303:
278:
274:
269:
236:
232:
227:
200:
196:
184:Turing machine
180:
179:
176:
164:
161:
152:
151:
131:
127:
122:
106:
95:
94:
90:
81:model and the
79:Turing-machine
74:
71:
50:model and the
48:Turing-machine
24:
14:
13:
10:
9:
6:
4:
3:
2:
685:
674:
671:
670:
668:
654:
652:3-540-44389-4
648:
644:
640:
634:
631:
627:
623:
619:
613:
609:
605:
601:
600:
595:
591:
587:
581:
579:
577:
573:
566:
564:
558:
555:
552:
549:
548:
547:
545:
541:
533:
531:
529:
525:
521:
517:
512:
498:
478:
470:
450:
447:
444:
441:
438:
435:
432:
426:
403:
400:
397:
394:
391:
388:
385:
379:
359:
339:
331:
327:
321:
305:
301:
276:
272:
267:
258:
254:
234:
230:
225:
216:
198:
194:
185:
177:
174:
173:
172:
170:
162:
160:
158:
149:
129:
125:
120:
111:
107:
104:
100:
99:
98:
91:
88:
87:
86:
84:
80:
72:
70:
68:
63:
61:
57:
53:
49:
45:
41:
36:
35:
30:
19:
642:
633:
598:
562:
543:
539:
537:
527:
515:
513:
468:
322:
252:
214:
181:
166:
156:
153:
109:
96:
76:
67:optimization
64:
59:
55:
43:
40:running time
39:
32:
26:
567:References
534:Subtleties
528:magnitudes
163:Definition
44:input size
448:
436:
401:
389:
93:operands.
667:Category
596:(1993),
626:1261419
469:lengths
649:
624:
614:
251:with
647:ISBN
612:ISBN
491:and
352:and
101:The
54:. A
31:, a
604:doi
471:of
445:log
433:log
398:log
386:log
146:by
85::
27:In
669::
622:MR
620:,
610:,
592:;
588:;
575:^
159:.
69:.
655:.
606::
544:b
540:a
499:b
479:a
454:)
451:b
442:+
439:a
430:(
427:O
407:)
404:b
395:+
392:a
383:(
380:O
360:b
340:a
306:n
302:2
277:n
273:2
268:2
253:n
235:n
231:2
226:2
215:n
199:n
195:2
130:n
126:2
121:2
110:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.