676:
But that probably won't be immediately obvious to readers, so perhaps we should specifically mention that fact in the article. I suppose that when I was writing, I gave more priority to clarity and educating the reader, instead of flow. However, I think some of the examples should go back in, because they'll make the article easier to understand for people who aren't familiar with computer science. I think we can include examples and still make it flow. Whether prose is easier to read than a list is a matter of personal preference. Also, I don't think there are any
Knowledge guidelines which specify that prose is preferred over lists. Correct me if I'm wrong. On the other hand, I suppose that when one reads an encyclopedia, they expect to see mostly paragraphs and not lists. I agree that references need to be added. Also, I noticed that your version doesn't include any discussion of the speed of hardware, while the previous version did. Did you think that point was invalid? I won't kill any of your children, but I might resurrect some of mine.Ā :) Navigatr85 22:49, 8 July 2008 (UTC)
804:
experiment, and it's not meant to be implemented on an actual computer. The purpose of the thought experiment is to show that there are exceptions to Cobham's rule. Similarly, the googolplex CPU is also a thought experiment, not meant to be implemented, and its purpose is also to show an exception to the rule. Also, I don't understand why a computer that executes 1 instruction every 5 years is not plausible. A clock rate in that range could be achieved, for example, by starting a tradition in which a person presses a button on a mechanical computer at the beginning of each Summer
Olympics. Yes, I know that example is silly, and there would never be any reason to build such a thing. But, remember, an algorithm with a runtime of 10n is also silly, and there would never be any reason to write a program with that runtime. I don't think my examples should be bound by the real world, if there are already other examples that are not bound by the the real world.
1237:, but they particularly apply to Cobham's thesis since it makes an explicit claim about practicality. Under Cobham's thesis, we are to call a problem for which the best algorithm takes 10n instructions feasible, and a problem with an algorithm that takes 2 infeasibleāeven though we could never solve an instance of size n=1 with the former algorithm, whereas we could solve an instance of the latter problem of size n=10 without difficulty. As we saw, it takes a day on a typical modern machine to process 2 operations when n=46; this may be the size of inputs we have, and the amount of time we have to solve a typical problem, making the 2-time algorithm feasible in practice on the inputs we have. Conversely, in fields where practical problems have millions of variables (such as
87:
77:
53:
363:
193:
175:
286:
265:
653:
examples because I felt they got in the way of the flow, although they were educational individually. The new section is in prose, and hopefully should be easier to read. It still reads as he said / she said, and it lacks any references (I didn't feel like citing my discussions with colleagues). Having killed a thousand of your favourite children, I now fully expect you to return the favour.
634:
Dcoetzee's post disproves my statement that polynomials with large exponents don't occur in "natural problems." And there are a few other things that I'm not 100% sure about. Also, I only have one citation. I guess I'm bending the rules of
Knowledge here. But please correct my mistakes, add citations, and continue to discuss here on the talk page. Thanks. Navigatr85 03:47, 1 April 2008 (UTC)
1151:
22:
1089:
791:
There is no natural problem whose best algorithm has that runtime. It is possible to imagine such a problem, but that problem would never occur in real life applications, and would not be useful at all. Similarly, it is possible to imagine a CPU that can do a googolplex operations in a second, but that CPU cannot be built in real life.
790:
Yes, my examples could be called ridiculous, but I think some of the other examples in the article are also ridiculous, and I think this ridiculousness is actually necessary to illustrate the point. One of the other examples given was an algorithm with a runtime of 10n, which is a ridiculous runtime.
980:, where the problem size increases but the individual numbers are bounded in size. For problems that fit this description, modern exponential-time algorithms demonstrate a quadratic growth over approximately 4 orders of magnitude on typical instances, which may be sufficient for many applications..
750:
Although hardware certainly has an effect on performance, the examples added are ridiculous. The entire span of computers ever constructed is perhaps 10 instructions per second (with relays) to 10 per second for a machine that has 1,000,000 fairly fast processors. So a machine with 10 instructions
675:
Thank you for taking my points into consideration. I didn't even realize that it was April Fool's Day when I made those comments. I'm glad it was clear to you that they weren't an April Fool's joke. Now that you mention it, I agree that changing the exponent and changing the base are the same thing.
638:
I think this is a good start - I think it's important to include something about the large exponents occurring in families of approximation algorithms. I also disagree strongly with the statement that "when we look at the running times of exponential algorithms that solve useful problems, almost all
947:
The typical response to this objection is that in general, algorithms for computational problems that naturally occur in computer science and in other fields have neither enormous nor minuscule constants and exponents. Even when a polynomial-time algorithm has a large exponent, historically, other
803:
If you are willing to consider algorithms that violate the rules of what is useful in real life, then should I also say that none of your statements can be trusted? No, of course I shouldn't. The algorithm with a 10n runtime violates the rules of what is useful, but it's really more like a thought
633:
OK, more thoughts: I not only copied things from the P=NP article, but also added some things. For some of the stuff I added, I'm not 100% sure about it. For example, I'm not totally sure that "Algorithms for problems that occur in practice typically have coefficients between 1/100 and 100." Also,
825:
Also, I would like to add that I've changed my mind, and the information about hardware actually DOESN'T belong in the article. The reason it doesn't belong is simply because it's never been published before, and therefore there would be no way to have a citation for it. But I think the point is
755:
more progress than has been achieved to date. Furthermore, if you are willing to consider machines that violate the laws of physics as we know them, then no statement can be trusted. On the other end of the spectrum, a computer that executes 1 instruction every 5 years is roughly 10 than any
652:
I largely rewrote the section, taking all your points into consideration (despite the date on which you made them), but cutting out many specifics. In particular, changing the exponent and changing the base are the same thing, so I only discussed the exponent. I removed many of the specific
629:
I just added these two sections. This is part of the process of moving a section out of the P=NP article into this article. I'm busy right now, but later on I'll delete the info from the P=NP article, and I'll post some more thoughts here on the talk page. Navigatr85 00:39, 1 April 2008 (UTC)
911:
I deleted a huge chunk of a basically useful and correct but misplaced text. Contrary to the opinion of the contributors (unreferenced, by the way), none of the below constitutes an objection. In fact, all of the below are approaches specifically developed to deal with inherent complexity of
963:
can often be solved exactly even with input sizes in the tens or hundreds of thousands. Even though the same algorithms can be made to fail (take too long, use too much memory, or trigger an error condition) on some inputs, users may be content with only sometimes getting solutions.
1068:
exist, if they have meaning, they must have recourse in the event that they are unheeded. This action has been tagged for more than 7 years, and a little superficial checking shows it has been unsourced over a long period as well. It is placed here, someone can add the citations.
384:
916:
of the real-world problem: put restrictions on the input, on the desired answer, etc. And by the way, simplex-algorithm is a popular but outdated example: it used to work best, but with recent advances polynomial-time algorithms are starting to beat it.
1350:
SHA-256 computations per year (not sure how many miners are around, not sure one could consider the mining community as a polynomially sized circuit, but still). I don't know how many bit-operations are required for each hash, but I think the example of
948:
algorithms are subsequently developed that improve the exponent. Also, typically, when computers are finally able to solve problems of size n fast enough, users of computers ask them to solve problems of size n+1. These are all subjective statements.
971:
is one such example, typically preferred to polynomial-time algorithms for the same problem because it runs in linear time on most practical input even though it occasionally requires exponential time. Another example is the typechecking algorithm for
1404:
being infeasible may be getting out of date... Changing the exponent for 128 or 192 should do the trick (and if this becomes outdated, we'll have bigger cryptographic issues to deal with than the accuracy of an example on a wiki page š¬).
756:
plausible implementation, and hence is a poor strawman as well. So if you want to make this argument, I think you should be bounded by the slowest plausible computer on one end, and the laws of physics as we understand them on the other.
639:
of them have a base of 2 or more." I've seen a number of problems with bases in the range of 1.2 to 1.8 (unfortunately I can't come up with one at the moment). I agree with the conclusion that bases very close to 1 are very unusual.
1273:
At a cursory glance, the article fails to adequately describe the impact on the development of the computational complexity theory. Unfortunately I am an average software eng and lack the expertise to address this deficiency.
856:
I didn't remember I had left this question here, but it looks like I'll have to answer it myself.Ā :-( I've added a couple of sources, but eventually they need to be rewritten describing who did what.
1433:
408:
611:
I suggest at some point that we discuss the fact that some natural approximation algorithms have algorithms with very large exponents (this was the motivation for the definition of the class
157:
548:
465:
403:
1348:
1320:
is considered as an infeasible amount of computation. While I was of this opinion until recent years, to my dismay it seems that currently the bitcoin community is running
1468:
710:
Since no one has responded with any objections, I'm going to add the information about hardware again, which
Bhudson had deleted. Navigatr85 01:09, 26 April 2009 (UTC)
336:
326:
1376:
1318:
1211:" means "hard, slow, and impractical." But this is not always true. To begin with, it abstracts away some important variables that influence the runtime in practice:
1402:
1473:
1453:
920:
These are major issues. I can continue and proceed with nit-picking with some other blunders, but for now it is an overkill: the whole text mostly unreferenced.
241:
1463:
967:
In some cases, in fact, an algorithm that might require exponential time is the technique of choice because it only does so on highly contrived examples. The
928:
considers families of polynomial-time algorithms where the exponent may depend on the desired error rate Īµ. For example, a PTAS algorithm may have runtime O(
302:
1443:
510:
247:
147:
1438:
133:
484:
1172:
1448:
349:
293:
270:
109:
573:
1409:
Agree. I did the same calculation and bitcoin mining is getting close. So I changed the example to n, which should be a safe statement.
941:
925:
217:
796:"Furthermore, if you are willing to consider machines that violate the laws of physics as we know them, then no statement can be trusted."
1009:
and the multiple-choice subset-sum problem are all solvable in linear time, provided the weights and profits are bounded by a constant.
893:
871:
456:
1064:
Policies mean something, or they do not. If the policy requiring verifiability and sourcing and those requiring that issues related to
841:
I remember reading something about this idea being due to
Edmonds (of the matching algorithm, etc.) Does someone know more about this?
1189:
1132:
437:
100:
58:
983:
This is an example of an algorithm that runs in polynomial time if the size of their inputs is bounded. These problems are called
726:
691:
1458:
529:
200:
180:
891:
1176:
1099:
960:
932:). This has been a practical problem in the design of approximation algorithms, and was mitigated by the introduction of
1242:
494:
375:
33:
956:
504:
418:
539:
301:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
870:
I've also heard
Edmonds mentioned in connection with this. Maybe in Garey and Johnson's book on NP-completeness.
985:
955:
problems can be solved quite effectively on many of the large inputs that appear in practice; in particular, the
566:
1161:
1114:
997:
976:. The graph at the top of this article shows the empirical complexity for solving a particular subset of the
1180:
1165:
1110:
897:
875:
21:
1234:
1219:
991:
213:
1414:
1279:
1258:
1050:
761:
475:
39:
86:
1275:
861:
846:
722:
714:
687:
679:
1323:
1238:
654:
216:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
108:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
1253:
Until it is sourced, and verifiable, please do not place it back in the article. Please comply.
1002:
92:
76:
52:
658:
394:
1410:
1354:
1296:
1254:
1046:
1006:
977:
757:
446:
298:
1203:
There are many lines of objection to Cobham's thesis. The thesis essentially states that "
857:
842:
827:
805:
718:
683:
1381:
1033:
Pisinger D (1999). "Linear Time
Algorithms for Knapsack Problems with Bounded Weights".
968:
520:
362:
139:
951:
Another objection is that Cobham's thesis only considers the worst-case inputs. Some
385:
Requested articles/Applied arts and sciences/Computer science, computing, and Internet
1427:
640:
616:
1065:
890:
Stephen Cook's Turing award lecture might be a useful reference for this article.
1150:
973:
105:
192:
174:
82:
427:
209:
1418:
1283:
1262:
1054:
901:
879:
865:
850:
831:
809:
765:
662:
643:
619:
285:
264:
205:
1020:
Goulimis C. N. (2007). "Appeal to NP-Completeness Considered Harmful".
952:
1117:. Statements consisting only of original research should be removed.
612:
1144:
1082:
503:
Find pictures for the biographies of computer scientists (see
142:
in the banner shell. Please resolve this conflict if possible.
138:
This article has been given a rating which conflicts with the
15:
615:). Not adding this right now since some expansion is coming.
1233:
All three are related, and are general complaints about
1045:
I leave it here, since it may be reused somewhere else.
1106:
1434:
Start-Class articles with conflicting quality ratings
1384:
1357:
1326:
1299:
1024:, Vol. 37, No. 6, NovemberāDecember 2007, pp. 584ā586
912:
intractable problems -- essentially by tweaking the
297:, a collaborative effort to improve the coverage of
204:, a collaborative effort to improve the coverage of
104:, a collaborative effort to improve the coverage of
1207:" means "easy, fast, and practical," while "not in
1396:
1370:
1342:
1312:
1215:It ignores constant factors and lower-order terms.
409:Computer science articles needing expert attention
246:This article has not yet received a rating on the
1201:
549:WikiProject Computer science/Unreferenced BLPs
1037:, Volume 33, Number 1, October 1999, pp. 1-14
8:
1179:. Unsourced material may be challenged and
940:polynomial-time approximation schemes; see
466:Computer science articles without infoboxes
404:Computer science articles needing attention
625:"Reasons" section and "Objections" section
370:Here are some tasks awaiting attention:
344:
259:
169:
47:
19:
1383:
1362:
1356:
1334:
1325:
1304:
1298:
1229:It ignores the typical size of the input.
1218:It ignores the size of the exponent. The
1190:Learn how and when to remove this message
1133:Learn how and when to remove this message
1469:Mid-importance Computer science articles
1013:
261:
171:
49:
1293:The Limitations section mentions that
1289:Minor comment on "limitations" example
1226:requiring arbitrarily large exponents.
995:; they are studied by the subfield of
311:Knowledge:WikiProject Computer science
1474:WikiProject Computer science articles
1454:Unknown-importance Computing articles
926:polynomial time approximation schemes
314:Template:WikiProject Computer science
7:
1464:Stub-Class Computer science articles
1222:proves the existence of problems in
1177:adding citations to reliable sources
942:polynomial time approximation scheme
291:This article is within the scope of
198:This article is within the scope of
98:This article is within the scope of
1249:) algorithms are often impractical.
751:per second represents more than 10
38:It is of interest to the following
1269:Description of mpact is inadequate
485:Timeline of computing 2020āpresent
140:project-independent quality rating
14:
1444:Mid-priority mathematics articles
1060:Moved long tagged OR section here
511:Computing articles needing images
118:Knowledge:WikiProject Mathematics
1439:Start-Class mathematics articles
1149:
1087:
361:
284:
263:
191:
173:
121:Template:WikiProject Mathematics
85:
75:
51:
20:
989:and are said to be solvable in
331:This article has been rated as
226:Knowledge:WikiProject Computing
152:This article has been rated as
1343:{\displaystyle \approx 2^{90}}
961:boolean satisfiability problem
229:Template:WikiProject Computing
1:
1449:Stub-Class Computing articles
851:23:02, 22 February 2009 (UTC)
565:Tag all relevant articles in
305:and see a list of open tasks.
220:and see a list of open tasks.
112:and see a list of open tasks.
1263:04:21, 1 February 2015 (UTC)
1243:Electronic Design Automation
574:WikiProject Computer science
350:WikiProject Computer science
294:WikiProject Computer science
1113:the claims made and adding
1055:00:57, 7 October 2011 (UTC)
957:travelling salesman problem
866:01:22, 20 August 2009 (UTC)
832:09:44, 24 August 2009 (UTC)
810:23:47, 19 August 2009 (UTC)
505:List of computer scientists
1490:
1284:17:48, 15 April 2016 (UTC)
902:09:26, 30 March 2011 (UTC)
880:09:26, 30 March 2011 (UTC)
826:still completely valid. --
766:02:46, 26 April 2009 (UTC)
620:20:02, 10 March 2008 (UTC)
337:project's importance scale
248:project's importance scale
1419:20:21, 22 July 2021 (UTC)
986:fixed-parameter tractable
663:00:42, 21 June 2008 (UTC)
567:Category:Computer science
343:
330:
317:Computer science articles
279:
245:
186:
151:
137:
70:
46:
998:parameterized complexity
644:17:39, 6 June 2008 (UTC)
607:Approximation algorithms
569:and sub-categories with
158:project's priority scale
1371:{\displaystyle n^{100}}
1313:{\displaystyle 2^{100}}
101:WikiProject Mathematics
1459:All Computing articles
1398:
1372:
1344:
1314:
1251:
1235:analysis of algorithms
1220:time hierarchy theorem
992:pseudo-polynomial time
530:Computer science stubs
214:information technology
28:This article is rated
1399:
1373:
1345:
1315:
1035:Journal of Algorithms
201:WikiProject Computing
1382:
1355:
1324:
1297:
1173:improve this section
1001:. For instance, the
348:Things you can help
124:mathematics articles
1397:{\displaystyle n=2}
1239:Operations Research
1394:
1368:
1340:
1310:
1098:possibly contains
1003:subset sum problem
232:Computing articles
93:Mathematics portal
34:content assessment
1200:
1199:
1192:
1143:
1142:
1135:
1100:original research
914:theoretical model
731:
717:comment added by
695:
682:comment added by
604:
603:
600:
599:
596:
595:
592:
591:
588:
587:
258:
257:
254:
253:
168:
167:
164:
163:
1481:
1403:
1401:
1400:
1395:
1377:
1375:
1374:
1369:
1367:
1366:
1349:
1347:
1346:
1341:
1339:
1338:
1319:
1317:
1316:
1311:
1309:
1308:
1195:
1188:
1184:
1153:
1145:
1138:
1131:
1127:
1124:
1118:
1115:inline citations
1091:
1090:
1083:
1038:
1031:
1025:
1018:
1007:knapsack problem
978:knapsack problem
730:
711:
677:
578:
572:
447:Computer science
376:Article requests
365:
358:
357:
345:
319:
318:
315:
312:
309:
308:Computer science
299:Computer science
288:
281:
280:
275:
271:Computer science
267:
260:
234:
233:
230:
227:
224:
195:
188:
187:
177:
170:
126:
125:
122:
119:
116:
95:
90:
89:
79:
72:
71:
66:
63:
55:
48:
31:
25:
24:
16:
1489:
1488:
1484:
1483:
1482:
1480:
1479:
1478:
1424:
1423:
1380:
1379:
1358:
1353:
1352:
1330:
1322:
1321:
1300:
1295:
1294:
1291:
1271:
1196:
1185:
1170:
1154:
1139:
1128:
1122:
1119:
1104:
1092:
1088:
1062:
1042:
1041:
1032:
1028:
1019:
1015:
909:
888:
839:
712:
627:
609:
584:
581:
576:
570:
558:Project-related
553:
534:
515:
489:
470:
451:
432:
413:
389:
316:
313:
310:
307:
306:
273:
231:
228:
225:
222:
221:
123:
120:
117:
114:
113:
91:
84:
64:
61:
32:on Knowledge's
29:
12:
11:
5:
1487:
1485:
1477:
1476:
1471:
1466:
1461:
1456:
1451:
1446:
1441:
1436:
1426:
1425:
1422:
1421:
1393:
1390:
1387:
1365:
1361:
1337:
1333:
1329:
1307:
1303:
1290:
1287:
1270:
1267:
1231:
1230:
1227:
1216:
1198:
1197:
1157:
1155:
1148:
1141:
1140:
1095:
1093:
1086:
1081:
1080:
1079:
1078:
1061:
1058:
1043:
1040:
1039:
1026:
1012:
1011:
969:simplex method
922:
908:
905:
887:
884:
883:
882:
868:
838:
835:
823:
822:
821:
820:
819:
818:
817:
816:
815:
814:
813:
812:
801:
800:
799:
798:
797:
777:
776:
775:
774:
773:
772:
771:
770:
769:
768:
739:
738:
737:
736:
735:
734:
733:
732:
701:
700:
699:
698:
697:
696:
668:
667:
666:
665:
647:
646:
626:
623:
608:
605:
602:
601:
598:
597:
594:
593:
590:
589:
586:
585:
583:
582:
580:
579:
562:
554:
552:
551:
545:
535:
533:
532:
526:
516:
514:
513:
508:
500:
490:
488:
487:
481:
471:
469:
468:
462:
452:
450:
449:
443:
433:
431:
430:
424:
414:
412:
411:
406:
400:
390:
388:
387:
381:
369:
367:
366:
354:
353:
341:
340:
333:Mid-importance
329:
323:
322:
320:
303:the discussion
289:
277:
276:
274:Midāimportance
268:
256:
255:
252:
251:
244:
238:
237:
235:
218:the discussion
196:
184:
183:
178:
166:
165:
162:
161:
150:
144:
143:
136:
130:
129:
127:
110:the discussion
97:
96:
80:
68:
67:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
1486:
1475:
1472:
1470:
1467:
1465:
1462:
1460:
1457:
1455:
1452:
1450:
1447:
1445:
1442:
1440:
1437:
1435:
1432:
1431:
1429:
1420:
1416:
1412:
1408:
1407:
1406:
1391:
1388:
1385:
1363:
1359:
1335:
1331:
1327:
1305:
1301:
1288:
1286:
1285:
1281:
1277:
1268:
1266:
1264:
1260:
1256:
1250:
1248:
1244:
1240:
1236:
1228:
1225:
1221:
1217:
1214:
1213:
1212:
1210:
1206:
1194:
1191:
1182:
1178:
1174:
1168:
1167:
1163:
1158:This section
1156:
1152:
1147:
1146:
1137:
1134:
1126:
1116:
1112:
1108:
1102:
1101:
1096:This section
1094:
1085:
1084:
1077:
1074:
1073:
1072:
1071:
1070:
1067:
1059:
1057:
1056:
1052:
1048:
1036:
1030:
1027:
1023:
1017:
1014:
1010:
1008:
1004:
1000:
999:
994:
993:
988:
987:
981:
979:
975:
970:
965:
962:
958:
954:
949:
945:
944:for details.
943:
939:
935:
931:
927:
924:The study of
921:
918:
915:
906:
904:
903:
899:
895:
894:75.57.242.120
892:
885:
881:
877:
873:
872:75.57.242.120
869:
867:
863:
859:
855:
854:
853:
852:
848:
844:
836:
834:
833:
829:
811:
807:
802:
795:
794:
793:
792:
789:
788:
787:
786:
785:
784:
783:
782:
781:
780:
779:
778:
767:
763:
759:
754:
749:
748:
747:
746:
745:
744:
743:
742:
741:
740:
728:
724:
720:
716:
709:
708:
707:
706:
705:
704:
703:
702:
693:
689:
685:
681:
674:
673:
672:
671:
670:
669:
664:
660:
656:
651:
650:
649:
648:
645:
642:
637:
636:
635:
631:
624:
622:
621:
618:
614:
606:
575:
568:
564:
563:
561:
559:
555:
550:
547:
546:
544:
542:
541:
536:
531:
528:
527:
525:
523:
522:
517:
512:
509:
506:
502:
501:
499:
497:
496:
491:
486:
483:
482:
480:
478:
477:
472:
467:
464:
463:
461:
459:
458:
453:
448:
445:
444:
442:
440:
439:
434:
429:
426:
425:
423:
421:
420:
415:
410:
407:
405:
402:
401:
399:
397:
396:
391:
386:
383:
382:
380:
378:
377:
372:
371:
368:
364:
360:
359:
356:
355:
351:
347:
346:
342:
338:
334:
328:
325:
324:
321:
304:
300:
296:
295:
290:
287:
283:
282:
278:
272:
269:
266:
262:
249:
243:
240:
239:
236:
219:
215:
211:
207:
203:
202:
197:
194:
190:
189:
185:
182:
179:
176:
172:
159:
155:
149:
146:
145:
141:
135:
132:
131:
128:
111:
107:
103:
102:
94:
88:
83:
81:
78:
74:
73:
69:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
1292:
1272:
1252:
1246:
1232:
1223:
1208:
1204:
1202:
1186:
1171:Please help
1159:
1129:
1120:
1097:
1075:
1063:
1044:
1034:
1029:
1021:
1016:
996:
990:
984:
982:
966:
950:
946:
937:
933:
929:
923:
919:
913:
910:
907:deleted text
889:
886:Cook lecture
840:
824:
752:
632:
628:
610:
557:
556:
540:Unreferenced
538:
537:
519:
518:
493:
492:
474:
473:
455:
454:
436:
435:
417:
416:
393:
392:
374:
373:
332:
292:
199:
154:Mid-priority
153:
99:
65:Midāpriority
40:WikiProjects
1411:LouScheffer
1276:Staszek Lem
1255:Leprof 7272
1047:Max Longint
974:Standard ML
758:LouScheffer
713:āPreceding
678:āPreceding
115:Mathematics
106:mathematics
62:Startāclass
59:Mathematics
1428:Categories
1245:), even O(
1107:improve it
1076:Objections
1022:Interfaces
1005:, the 0-1
858:Shreevatsa
843:Shreevatsa
828:Navigatr85
806:Navigatr85
719:Navigatr85
684:Navigatr85
30:Stub-class
1160:does not
1111:verifying
934:efficient
428:Computing
223:Computing
210:computing
206:computers
181:Computing
1265:Le Prof
1123:May 2008
959:and the
837:Edmonds?
727:contribs
715:unsigned
692:contribs
680:unsigned
641:Dcoetzee
617:Dcoetzee
476:Maintain
419:Copyedit
1181:removed
1166:sources
1105:Please
953:NP-hard
655:Bhudson
457:Infobox
395:Cleanup
335:on the
156:on the
438:Expand
212:, and
36:scale.
1066:WP:OR
938:fully
753:times
613:FPTAS
521:Stubs
495:Photo
352:with:
134:Start
1415:talk
1378:for
1280:talk
1259:talk
1164:any
1162:cite
1051:talk
936:and
898:talk
876:talk
862:talk
847:talk
762:talk
723:talk
688:talk
659:talk
1364:100
1306:100
1241:or
1175:by
1109:by
327:Mid
242:???
148:Mid
1430::
1417:)
1336:90
1328:ā
1282:)
1261:)
1053:)
900:)
878:)
864:)
849:)
830:,
808:,
764:)
729:)
725:ā¢
694:)
690:ā¢
661:)
577:}}
571:{{
208:,
1413:(
1392:2
1389:=
1386:n
1360:n
1332:2
1302:2
1278:(
1257:(
1247:n
1224:P
1209:P
1205:P
1193:)
1187:(
1183:.
1169:.
1136:)
1130:(
1125:)
1121:(
1103:.
1049:(
930:n
896:(
874:(
860:(
845:(
760:(
721:(
686:(
657:(
560::
543::
524::
507:)
498::
479::
460::
441::
422::
398::
379::
339:.
250:.
160:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.