CINXE.COM

<!DOCTYPE html> <html class="client-nojs skin-theme-clientpref-day mf-expand-sections-clientpref-0 mf-font-size-clientpref-small mw-mf-amc-clientpref-0" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Talk:BPP (complexity) - Wikipedia</title> <script>(function(){var className="client-js skin-theme-clientpref-day mf-expand-sections-clientpref-0 mf-font-size-clientpref-small mw-mf-amc-clientpref-0";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"d68f13d4-2c91-47c3-8934-4ae48a321b8b","wgCanonicalNamespace":"Talk","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":1,"wgPageName":"Talk:BPP_(complexity)","wgTitle":"BPP (complexity)","wgCurRevisionId":1200310634,"wgRevisionId":1200310634, "wgArticleId":4758,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Talk:BPP_(complexity)","wgRelevantArticleId":4758,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFMode":"stable","wgMFAmc":false,"wgMFAmcOutreachActive":false,"wgMFAmcOutreachUserEligible":false,"wgMFLazyLoadImages":true,"wgMFEditNoticesFeatureConflict":false,"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgMFIsSupportedEditRequest":true, "wgMFScriptPath":"","wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":true,"wgEditSubmitButtonLabelPublish":true,"wgDiscussionToolsFeaturesEnabled":{"replytool":true,"newtopictool":true,"sourcemodetoolbar":true,"topicsubscription":false,"autotopicsub":false,"visualenhancements":true,"visualenhancements_reply":true,"visualenhancements_pageframe":true},"wgDiscussionToolsFallbackEditMode":"source","wgSectionTranslationTargetLanguages":["ace","ady","alt","am","ami","an","ang","ann","anp","ar","ary","arz","as","ast","av","avk","awa","ay","az","azb","ba","ban","bar","bbc","bcl","bdr","be","bew","bg","bho","bi","bjn","blk","bm","bn","bo","bpy","br","bs","btm","bug","ca","cdo","ce","ceb","ch","chr","ckb","co","cr","crh","cs","cu","cy","da","dag","de","dga","din","diq","dsb","dtp","dv","dz","ee","el","eml","eo","es","et","eu","fa","fat","ff","fi","fj","fo","fon","fr","frp","frr","fur","fy","gag","gan","gcr","gl","glk", "gn","gom","gor","gpe","gu","guc","gur","guw","gv","ha","hak","haw","he","hi","hif","hr","hsb","ht","hu","hy","hyw","ia","iba","ie","ig","igl","ilo","io","is","it","iu","ja","jam","jv","ka","kaa","kab","kbd","kbp","kcg","kg","kge","ki","kk","kl","km","kn","ko","koi","krc","ks","ku","kus","kv","kw","ky","lad","lb","lez","lg","li","lij","lld","lmo","ln","lo","lt","ltg","lv","mad","mai","map-bms","mdf","mg","mhr","mi","min","mk","ml","mn","mni","mnw","mos","mr","mrj","ms","mt","mwl","my","myv","mzn","nah","nan","nap","nb","nds","nds-nl","ne","new","nia","nl","nn","nqo","nr","nso","ny","oc","om","or","os","pa","pag","pam","pap","pcd","pcm","pdc","pl","pms","pnb","ps","pt","pwn","qu","rm","rn","ro","rsk","rue","rup","rw","sa","sah","sat","sc","scn","sco","sd","se","sg","sgs","sh","shi","shn","si","sk","skr","sl","sm","smn","sn","so","sq","sr","srn","ss","st","stq","su","sv","sw","szl","ta","tay","tcy","tdd","te","tet","tg","th","ti","tk","tl","tly","tn","to","tpi","tr","trv","ts","tt","tum" ,"tw","ty","tyv","udm","ur","uz","ve","vec","vep","vi","vls","vo","vro","wa","war","wo","wuu","xal","xh","xmf","yi","yo","yue","za","zgh","zh","zu"],"isLanguageSearcherCXEntrypointEnabled":false,"mintEntrypointLanguages":["ace","ast","azb","bcl","bjn","bh","crh","ff","fon","ig","is","ki","ks","lmo","min","sat","ss","tn","vec"],"wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false,"wgMinervaPermissions":{"watchable":true,"watch":false},"wgMinervaFeatures":{"beta":false,"donate":true,"mobileOptionsLink":true,"categories":false,"pageIssues":true,"talkAtTop":true,"historyInPageActions":false,"overflowSubmenu":false,"tabsOnSpecials":true,"personalMenu":false,"mainMenuExpanded":false,"echo":true,"nightMode":true}, "wgMinervaDownloadNamespaces":[0]};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.discussionTools.init.styles":"ready","oojs-ui-core.styles":"ready","oojs-ui.styles.indicators":"ready","mediawiki.widgets.styles":"ready","oojs-ui-core.icons":"ready","oojs-ui.styles.icons-content":"ready","oojs-ui.styles.icons-interactions":"ready","oojs-ui.styles.icons-editing-core":"ready","skins.minerva.styles":"ready","skins.minerva.content.styles.images":"ready","mediawiki.hlist":"ready","skins.minerva.codex.styles":"ready","skins.minerva.icons":"ready","skins.minerva.amc.styles":"ready","ext.wikimediamessages.styles":"ready","mobile.init.styles":"ready","oojs-ui.styles.icons-alerts":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["site","mediawiki.page.ready","skins.minerva.scripts","ext.centralNotice.geoIP","ext.centralNotice.startUp", "ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","ext.popups","mobile.init","ext.echo.centralauth","ext.discussionTools.init","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.cx.eventlogging.campaigns","ext.cx.entrypoints.languagesearcher.init","mw.externalguidance.init","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.discussionTools.init.styles%7Cext.math.styles%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cmediawiki.hlist%7Cmediawiki.widgets.styles%7Cmobile.init.styles%7Coojs-ui-core.icons%2Cstyles%7Coojs-ui.styles.icons-alerts%2Cicons-content%2Cicons-editing-core%2Cicons-interactions%2Cindicators%7Cskins.minerva.amc.styles%7Cskins.minerva.codex.styles%7Cskins.minerva.content.styles.images%7Cskins.minerva.icons%2Cstyles&only=styles&skin=minerva"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=minerva"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=minerva"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="theme-color" content="#eaecf0"> <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes, minimum-scale=0.25, maximum-scale=5.0"> <meta property="og:title" content="Talk:BPP (complexity) - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="manifest" href="/w/api.php?action=webapp-manifest"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="ext-discussiontools-replytool-enabled ext-discussiontools-newtopictool-enabled ext-discussiontools-sourcemodetoolbar-enabled ext-discussiontools-visualenhancements-enabled ext-discussiontools-visualenhancements_reply-enabled ext-discussiontools-visualenhancements_pageframe-enabled collapsible-headings-collapsed ext-discussiontools-init-lede-hidden ext-discussiontools-init-new-topic-opened mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-1 ns-talk mw-editable page-Talk_BPP_complexity rootpage-Talk_BPP_complexity stable skin-minerva action-view skin--responsive mw-mf-amc-disabled mw-mf"><div id="mw-mf-viewport"> <div id="mw-mf-page-center"> <a class="mw-mf-page-center__mask" href="#"></a> <header class="header-container header-chrome"> <div class="minerva-header"> <nav class="navigation-drawer toggle-list view-border-box"> <input type="checkbox" id="main-menu-input" class="toggle-list__checkbox" role="button" aria-haspopup="true" aria-expanded="false" aria-labelledby="mw-mf-main-menu-button"> <label role="button" for="main-menu-input" id="mw-mf-main-menu-button" aria-hidden="true" data-event-name="ui.mainmenu" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet toggle-list__toggle"> <span class="minerva-icon minerva-icon--menu"></span> <span></span> </label> <div id="mw-mf-page-left" class="menu view-border-box"> <ul id="p-navigation" class="toggle-list__list"> <li class="toggle-list-item "> <a class="toggle-list-item__anchor menu__item--home" href="/wiki/Main_Page" data-mw="interface"> <span class="minerva-icon minerva-icon--home"></span> <span class="toggle-list-item__label">Home</span> </a> </li> <li class="toggle-list-item "> <a class="toggle-list-item__anchor menu__item--random" href="/wiki/Special:Random" data-mw="interface"> <span class="minerva-icon minerva-icon--die"></span> <span class="toggle-list-item__label">Random</span> </a> </li> <li class="toggle-list-item skin-minerva-list-item-jsonly"> <a class="toggle-list-item__anchor menu__item--nearby" href="/wiki/Special:Nearby" data-event-name="menu.nearby" data-mw="interface"> <span class="minerva-icon minerva-icon--mapPin"></span> <span class="toggle-list-item__label">Nearby</span> </a> </li> </ul> <ul id="p-personal" class="toggle-list__list"> <li class="toggle-list-item "> <a class="toggle-list-item__anchor menu__item--login" href="/w/index.php?title=Special:UserLogin&returnto=Talk%3ABPP+%28complexity%29" data-event-name="menu.login" data-mw="interface"> <span class="minerva-icon minerva-icon--logIn"></span> <span class="toggle-list-item__label">Log in</span> </a> </li> </ul> <ul id="pt-preferences" class="toggle-list__list"> <li class="toggle-list-item skin-minerva-list-item-jsonly"> <a class="toggle-list-item__anchor menu__item--settings" href="/w/index.php?title=Special:MobileOptions&returnto=Talk%3ABPP+%28complexity%29" data-event-name="menu.settings" data-mw="interface"> <span class="minerva-icon minerva-icon--settings"></span> <span class="toggle-list-item__label">Settings</span> </a> </li> </ul> <ul id="p-donation" class="toggle-list__list"> <li class="toggle-list-item "> <a class="toggle-list-item__anchor menu__item--donate" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en&utm_key=minerva" data-event-name="menu.donate" data-mw="interface"> <span class="minerva-icon minerva-icon--heart"></span> <span class="toggle-list-item__label">Donate</span> </a> </li> </ul> <ul class="hlist"> <li class="toggle-list-item "> <a class="toggle-list-item__anchor menu__item--about" href="/wiki/Wikipedia:About" data-mw="interface"> <span class="toggle-list-item__label">About Wikipedia</span> </a> </li> <li class="toggle-list-item "> <a class="toggle-list-item__anchor menu__item--disclaimers" href="/wiki/Wikipedia:General_disclaimer" data-mw="interface"> <span class="toggle-list-item__label">Disclaimers</span> </a> </li> </ul> </div> <label class="main-menu-mask" for="main-menu-input"></label> </nav> <div class="branding-box"> <a href="/wiki/Main_Page"> <span><img src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" alt="Wikipedia" width="120" height="18" style="width: 7.5em; height: 1.125em;"/> </span> </a> </div> <form action="/w/index.php" method="get" class="minerva-search-form"> <div class="search-box"> <input type="hidden" name="title" value="Special:Search"/> <input class="search skin-minerva-search-trigger" id="searchInput" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f"> <span class="search-box-icon-overlay"><span class="minerva-icon minerva-icon--search"></span> </span> </div> <button id="searchIcon" class="cdx-button cdx-button--size-large cdx-button--icon-only cdx-button--weight-quiet skin-minerva-search-trigger"> <span class="minerva-icon minerva-icon--search"></span> <span>Search</span> </button> </form> <nav class="minerva-user-navigation" aria-label="User navigation"> </nav> </div> </header> <main id="content" class="mw-body"> <div class="banner-container"> <div id="siteNotice"></div> </div> <div class="pre-content heading-holder"> <div class="page-heading"> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-namespace">Talk</span><span class="mw-page-title-separator">:</span><span class="mw-page-title-main">BPP (complexity)</span></h1> <div class="tagline"></div> </div> <ul id="p-associated-pages" class="minerva__tab-container"> <li class="minerva__tab "> <a class="minerva__tab-text" href="/wiki/BPP_(complexity)" rel="" data-event-name="tabs.subject">Article</a> </li> <li class="minerva__tab selected"> <a class="minerva__tab-text" href="/wiki/Talk:BPP_(complexity)" rel="discussion" data-event-name="tabs.talk">Talk</a> </li> </ul> <nav class="page-actions-menu"> <ul id="p-views" class="page-actions-menu__list"> <li id="language-selector" class="page-actions-menu__list-item"> <a role="button" href="" data-mw="interface" data-event-name="menu.languages" title="Language" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet language-selector disabled"> <span class="minerva-icon minerva-icon--language"></span> <span>Language</span> </a> </li> <li id="page-actions-watch" class="page-actions-menu__list-item"> <a role="button" id="ca-watch" href="/w/index.php?title=Special:UserLogin&returnto=Talk%3ABPP+%28complexity%29" data-event-name="menu.watch" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet menu__item--page-actions-watch"> <span class="minerva-icon minerva-icon--star"></span> <span>Watch</span> </a> </li> <li id="page-actions-edit" class="page-actions-menu__list-item"> <a role="button" id="ca-edit" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit" data-event-name="menu.edit" data-mw="interface" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet edit-page menu__item--page-actions-edit"> <span class="minerva-icon minerva-icon--edit"></span> <span>Edit</span> </a> </li> </ul> </nav>  <div id="mw-content-subtitle"><div class="ext-discussiontools-init-pageframe-latestcomment">Latest comment: <a href="#c-Bilorv-20230128134100-62.166.189.223-20230125103300">1 year ago</a> by Bilorv in topic <a href="#k_runs">k runs</a></div></div> </div> <div id="bodyContent" class="content"> <div id="mw-content-text" class="mw-body-content"><div class="ext-discussiontools-init-lede-button-container"><span id='ooui-php-29' class='ext-discussiontools-init-lede-button oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"info","label":"Learn more about this page","classes":["ext-discussiontools-init-lede-button"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-info'></span><span class='oo-ui-labelElement-label'>Learn more about this page</span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span></div><script>function mfTempOpenSection(id){var block=document.getElementById("mf-section-"+id);block.className+=" open-block";block.previousSibling.className+=" open-block";}</script><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><section class="mf-section-0" id="mf-section-0"><style data-mw-deduplicate="TemplateStyles:r1237879475">.mw-parser-output .tmbox{margin:4px 0;border-collapse:collapse;border:1px solid #c0c090;background-color:#f8eaba;box-sizing:border-box}.mw-parser-output .tmbox.mbox-small{font-size:88%;line-height:1.25em}.mw-parser-output .tmbox-speedy{border:2px solid #b32424;background-color:#fee7e6}.mw-parser-output .tmbox-delete{border:2px solid #b32424}.mw-parser-output .tmbox-content{border:2px solid #f28500}.mw-parser-output .tmbox-style{border:2px solid #fc3}.mw-parser-output .tmbox-move{border:2px solid #9932cc}.mw-parser-output .tmbox .mbox-text{border:none;padding:0.25em 0.9em;width:100%}.mw-parser-output .tmbox .mbox-image{border:none;padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .tmbox .mbox-imageright{border:none;padding:2px 0.9em 2px 0;text-align:center}.mw-parser-output .tmbox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .tmbox .mbox-invalid-type{text-align:center}@media(min-width:720px){.mw-parser-output .tmbox{margin:4px 10%}.mw-parser-output .tmbox.mbox-small{clear:right;float:right;margin:4px 0 4px 1em;width:238px}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmbox{background-color:#2e2505}html.skin-theme-clientpref-night .mw-parser-output .tmbox-speedy{background-color:#310402}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmbox{background-color:#2e2505}html.skin-theme-clientpref-os .mw-parser-output .tmbox-speedy{background-color:#310402}}body.skin--responsive .mw-parser-output table.tmbox img{max-width:none!important}</style><style data-mw-deduplicate="TemplateStyles:r1243927654">.mw-parser-output .banner-shell{border-collapse:separate;border-spacing:4px}.mw-parser-output .banner-shell-header{text-align:center;font-weight:bold}.mw-parser-output .banner-shell-inner{padding:2px 4px;background:#fffaef;color:inherit;border:1px dotted gray}@media screen{html.skin-theme-clientpref-night .mw-parser-output .banner-shell-inner{background:#2e2505}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .banner-shell-inner{background:#2e2505}}.mw-parser-output .banner-shell .tmbox{margin:2px 0;width:100%}.mw-parser-output .banner-shell .tmbox.mbox-small{line-height:1.5em;font-size:100%}.mw-parser-output .banner-shell-inner .banner-shell-outside{display:none}@media(min-width:720px){.mw-parser-output .wpbs{width:80%}}.mw-parser-output .wpbs .assess{width:60px;text-align:center}.mw-parser-output .wpbs .banner-shell-header{border:none;padding:0.25em 0.9em 0.25em 0}.mw-parser-output .wpbs .wpb .wpb-header{display:table-row}.mw-parser-output .wpbs .wpb:not(.mw-collapsed) .wpb-header-icon a{display:none}</style><table role="presentation" class="tmbox tmbox-notice banner-shell wpbs mw-collapsible"><tbody><tr><td class="assess"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Symbol_start_class.svg" class="mw-file-description" title="Start-Class article"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/a/a4/Symbol_start_class.svg/35px-Symbol_start_class.svg.png" decoding="async" width="35" height="36" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/a/a4/Symbol_start_class.svg/53px-Symbol_start_class.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/a/a4/Symbol_start_class.svg/70px-Symbol_start_class.svg.png 2x" data-file-width="180" data-file-height="185"></a></span></td><td class="banner-shell-header" style="text-align:left;font-weight:normal">This article is rated <b>Start-class</b> on Wikipedia's <a href="/wiki/Wikipedia:Content_assessment" title="Wikipedia:Content assessment">content assessment</a> scale.<br>It is of interest to the following <a href="/wiki/Wikipedia:WikiProject" title="Wikipedia:WikiProject">WikiProjects</a>:</td></tr><tr><td colspan="2" class="banner-shell-inner outercollapse"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1237879475"><style data-mw-deduplicate="TemplateStyles:r1256394742">.mw-parser-output .wpb-header,.mw-parser-output .wpb-metadata,.mw-parser-output .wpb-iefix{display:none}.mw-parser-output .wpb-header-name{text-align:right;padding:0.3em 1em 0.3em 0.3em;width:50%;font-weight:bold}.mw-parser-output .wpb-header-assessment{text-align:left;width:50%;padding:0.3em}.mw-parser-output .wpb-header-combined{text-align:left;padding:0.3em 0.3em 0.3em 0;font-weight:bold}.mw-parser-output .wpb-header-bubbles{border-radius:.5em;padding:0 .3em;margin-left:0.5em;white-space:nowrap;font-weight:normal;color:black}.mw-parser-output .wpb-nested-task-force{font-weight:normal}.mw-parser-output .wpb-header-icon{width:50px;text-align:center}.mw-parser-output .wpb-category-box{background-color:#F5F5F5;border-width:1px;width:500px}.mw-parser-output .wpbs .wpb .wpb-main{background-color:#FFFAEF;padding:3px 0 3px 0.7em}.mw-parser-output .wpb .wpb-main{padding:3px 5px}.mw-parser-output .wpbs .wpb-header{background-color:#FFFAEF}.mw-parser-output .wpb-main>table{background-color:transparent;border:none;padding:0;width:100%;border-spacing:0}.mw-parser-output .wpb .wpb-image{padding:2px 0}.mw-parser-output .wpb-collapsed-head{text-align:left;padding:0.2em 2px 0.2em 0}.mw-parser-output .wpb-collapsed-notes{padding:0}.mw-parser-output .wpb-collapsed-notes>table{width:100%;background-color:transparent}.mw-parser-output .wpb .wpb-gutter{padding:2px 0 0 0}.mw-parser-output .wpbs .banner-shell-inner{background-color:#f8eaba;border:none}.mw-parser-output .wpb-table{table-layout:fixed}@media(min-width:720px){.mw-parser-output .wpb{min-width:80%}}.mw-parser-output .assess{font-weight:bold;text-align:center;white-space:nowrap;color:black}.mw-parser-output .import-top{background-color:#FFBFFF}.mw-parser-output .import-high{background-color:#FFCCFF}.mw-parser-output .import-mid{background-color:#FFD9FF}.mw-parser-output .import-low{background-color:#FFE7FF}.mw-parser-output .import-bottom{background-color:#FFEBFF}.mw-parser-output .import-na{background-color:#F5F5F5}.mw-parser-output .import-unknown{background-color:#DCDCDC}.mw-parser-output .class-fa,.mw-parser-output .class-fl,.mw-parser-output .class-fm{background-color:#BED3FF}.mw-parser-output .class-a,.mw-parser-output .class-al{background-color:#C0FFFF}.mw-parser-output .class-ga{background-color:#C0FFC0}.mw-parser-output .class-b,.mw-parser-output .class-bl{background-color:#DFFFBF}.mw-parser-output .class-c,.mw-parser-output .class-cl{background-color:#FFFFBE}.mw-parser-output .class-start{background-color:#FFDBBF}.mw-parser-output .class-stub,.mw-parser-output .class-sl{background-color:#FFC0C0}.mw-parser-output .class-list{background-color:#D2C0FF}.mw-parser-output .class-na{background-color:#F5F5F5}.mw-parser-output .class-category{background-color:#FFDB58}.mw-parser-output .class-disambig{background-color:#00FA9A}.mw-parser-output .class-draft{background-color:#E7B198}.mw-parser-output .class-file{background-color:#DDCCFF}.mw-parser-output .class-future{background-color:#B4BBFF}.mw-parser-output .class-portal{background-color:#DDB1BC}.mw-parser-output .class-project{background-color:#C0C090}.mw-parser-output .class-redirect{background-color:#C0C0C0}.mw-parser-output .class-sia{background-color:#E9DAFF}.mw-parser-output .class-user{background-color:#DDD06A}.mw-parser-output .class-template{background-color:#FBCEB1}.mw-parser-output .class-unassessed{background-color:#DCDCDC}.mw-parser-output .conflict{border:0.2em solid red}.mw-parser-output .inactive-wikiproject .wpb-header-bubbles{color:inherit}@media screen{html.skin-theme-clientpref-night .mw-parser-output .wpb-category-box{background-color:#0a0a0a}html.skin-theme-clientpref-night .mw-parser-output .wpbs .wpb .wpb-main,html.skin-theme-clientpref-night .mw-parser-output .wpbs .wpb-header{background-color:#302f2d}html.skin-theme-clientpref-night .mw-parser-output .wpbs .banner-shell-inner{background-color:#2e2505}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .wpb-category-box{background-color:#0a0a0a}html.skin-theme-clientpref-os .mw-parser-output .wpbs .wpb .wpb-main,html.skin-theme-clientpref-os .mw-parser-output .wpbs .wpb-header{background-color:#302f2d}html.skin-theme-clientpref-os .mw-parser-output .wpbs .banner-shell-inner{background-color:#2e2505}}</style><table class="tmbox tmbox-notice mw-collapsible innercollapse wpb wpb-table"><tbody><tr class="wpb-header"><td class="wpb-header-icon"><span typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics-p.svg" class="mw-file-description"><img alt="WikiProject icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/25px-Nuvola_apps_edu_mathematics-p.svg.png" decoding="async" width="25" height="25" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/38px-Nuvola_apps_edu_mathematics-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/50px-Nuvola_apps_edu_mathematics-p.svg.png 2x" data-file-width="128" data-file-height="128"></a></span></td><td class="wpb-header-combined"><a href="/wiki/Wikipedia:WikiProject_Mathematics" title="Wikipedia:WikiProject Mathematics">Mathematics</a> <span class="wpb-header-bubbles import-mid">Mid‑priority</span></td></tr><tr><td class="mbox-text wpb-main" colspan="2"><table><tbody><tr><td class="mbox-image wpb-image"><span typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics-p.svg" class="mw-file-description"><img alt="WikiProject icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/60px-Nuvola_apps_edu_mathematics-p.svg.png" decoding="async" width="60" height="60" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/90px-Nuvola_apps_edu_mathematics-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/120px-Nuvola_apps_edu_mathematics-p.svg.png 2x" data-file-width="128" data-file-height="128"></a></span></td><td class="mbox-text"><style data-mw-deduplicate="TemplateStyles:r1239009302">.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{clear:left;float:left;margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}</style><ul role="navigation" aria-label="Portals" class="noprint portalbox portalborder portalright"> <li class="portalbox-entry"><span class="portalbox-image"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics_blue-p.svg" class="mw-file-description"><img alt="icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/28px-Nuvola_apps_edu_mathematics_blue-p.svg.png" decoding="async" width="28" height="28" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/42px-Nuvola_apps_edu_mathematics_blue-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/56px-Nuvola_apps_edu_mathematics_blue-p.svg.png 2x" data-file-width="128" data-file-height="128"></a></span></span><span class="portalbox-link"><a href="/wiki/Portal:Mathematics" title="Portal:Mathematics">Mathematics portal</a></span></li></ul>This article is within the scope of <b><a href="/wiki/Wikipedia:WikiProject_Mathematics" title="Wikipedia:WikiProject Mathematics">WikiProject Mathematics</a></b>, a collaborative effort to improve the coverage of <a href="/wiki/Mathematics" title="Mathematics">mathematics</a> on Wikipedia. If you would like to participate, please visit the project page, where you can join <a href="/wiki/Wikipedia_talk:WikiProject_Mathematics" title="Wikipedia talk:WikiProject Mathematics">the discussion</a> and see a list of open tasks.<span class="metadata wpb-metadata"><span class="wpb-project">Mathematics</span><span class="wpb-project_link">Wikipedia:WikiProject Mathematics</span><span class="wpb-banner_name">Template:WikiProject Mathematics</span><span class="wpb-assessment_cat">mathematics articles</span></span></td><td class="mbox-empty-cell"></td></tr><tr><td class="assess import-mid"><a href="/wiki/Category:Mid-priority_mathematics_articles" title="Category:Mid-priority mathematics articles">Mid</a></td><td class="mbox-text" colspan="2">This article has been rated as <b>Mid-priority</b> on the <a href="/wiki/Wikipedia:WikiProject_Mathematics/Wikipedia_1.0/Assessment#Priority_scale" class="mw-redirect" title="Wikipedia:WikiProject Mathematics/Wikipedia 1.0/Assessment">project's priority scale</a>.</td></tr></tbody></table></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1237879475"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1256394742"><table class="tmbox tmbox-notice mw-collapsible innercollapse wpb wpb-table"><tbody><tr class="wpb-header"><td class="wpb-header-icon"><span typeof="mw:File"><a href="/wiki/File:LampFlowchart.svg" class="mw-file-description"><img alt="WikiProject icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/91/LampFlowchart.svg/18px-LampFlowchart.svg.png" decoding="async" width="18" height="25" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/91/LampFlowchart.svg/28px-LampFlowchart.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/91/LampFlowchart.svg/37px-LampFlowchart.svg.png 2x" data-file-width="324" data-file-height="442"></a></span></td><td class="wpb-header-combined"><a href="/wiki/Wikipedia:WikiProject_Computer_science" title="Wikipedia:WikiProject Computer science">Computer science</a> <span class="wpb-header-bubbles import-mid">Mid‑importance</span></td></tr><tr><td class="mbox-text wpb-main" colspan="2"><table><tbody><tr><td class="mbox-image wpb-image"><span typeof="mw:File"><a href="/wiki/File:LampFlowchart.svg" class="mw-file-description"><img alt="WikiProject icon" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/91/LampFlowchart.svg/80px-LampFlowchart.svg.png" decoding="async" width="80" height="109" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/91/LampFlowchart.svg/120px-LampFlowchart.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/91/LampFlowchart.svg/160px-LampFlowchart.svg.png 2x" data-file-width="324" data-file-height="442"></a></span></td><td class="mbox-text">This article is within the scope of <b><a href="/wiki/Wikipedia:WikiProject_Computer_science" title="Wikipedia:WikiProject Computer science">WikiProject Computer science</a></b>, a collaborative effort to improve the coverage of <a href="/wiki/Computer_science" title="Computer science">Computer science</a> related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join <a href="/wiki/Wikipedia_talk:WikiProject_Computer_science" title="Wikipedia talk:WikiProject Computer science">the discussion</a> and see a list of open tasks.<span class="metadata wpb-metadata"><span class="wpb-project">Computer science</span><span class="wpb-project_link">Wikipedia:WikiProject Computer science</span><span class="wpb-banner_name">Template:WikiProject Computer science</span><span class="wpb-assessment_cat">Computer science articles</span></span></td><td class="mbox-empty-cell"></td></tr><tr><td class="assess import-mid"><a href="/wiki/Category:Mid-importance_Computer_science_articles" title="Category:Mid-importance Computer science articles">Mid</a></td><td class="mbox-text" colspan="2">This article has been rated as <b>Mid-importance</b> on the <a href="/wiki/Wikipedia:WikiProject_Computer_science/Assessment#Importance_scale" title="Wikipedia:WikiProject Computer science/Assessment">project's importance scale</a>.</td></tr><tr><td colspan="3" style="padding:0"><table class="mw-collapsible mw-collapsed" style="background:transparent;width:100%"><tbody><tr><th style="text-align:left;padding:0.2em 2px 0.2em 0">Things you can help <a href="/wiki/Wikipedia:WikiProject_Computer_science" title="Wikipedia:WikiProject Computer science">WikiProject Computer science</a> with:</th></tr><tr><td style="text-align:left;padding:5px;background-color:white;border:1px solid #c0c090;margin-top:5px"> <table style="background:none;color:inherit;width:auto;"> <tbody><tr> <td style="vertical-align:top;"> <span typeof="mw:File"><a href="/wiki/File:Nuvola_apps_korganizer.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/e/e6/Nuvola_apps_korganizer.svg/50px-Nuvola_apps_korganizer.svg.png" decoding="async" width="50" height="50" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/e/e6/Nuvola_apps_korganizer.svg/75px-Nuvola_apps_korganizer.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/e/e6/Nuvola_apps_korganizer.svg/100px-Nuvola_apps_korganizer.svg.png 2x" data-file-width="128" data-file-height="128"></a></span><br><div style="width: 55px; height: 0px;"></div> </td> <td> <div style="position: relative; left: 0px; margin-right: 0px; z-index: 15;">Here are some tasks awaiting attention: <ul style="font-size: 100%; margin: 0px; padding: 0.3em 0px 0.3em 25px;"> <li><b><i><a href="/wiki/Wikipedia:Requested_articles" title="Wikipedia:Requested articles">Article requests</a></i> :</b> <div> <ul><li><a href="/wiki/Wikipedia:Requested_articles/Applied_arts_and_sciences/Computer_science,_computing,_and_Internet" title="Wikipedia:Requested articles/Applied arts and sciences/Computer science, computing, and Internet">Requested articles/Applied arts and sciences/Computer science, computing, and Internet</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Cleanup" title="Wikipedia:Cleanup">Cleanup</a></i> :</b> <div> <ul><li><a href="/wiki/Category:Computer_science_articles_needing_attention" title="Category:Computer science articles needing attention">Computer science articles needing attention</a></li> <li><a href="/wiki/Category:Computer_science_articles_needing_expert_attention" title="Category:Computer science articles needing expert attention">Computer science articles needing expert attention</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Basic_copyediting" title="Wikipedia:Basic copyediting">Copyedit</a></i> :</b> <div> <ul><li><a href="/wiki/Computing" title="Computing">Computing</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Writing_better_articles" title="Wikipedia:Writing better articles">Expand</a></i> :</b> <div> <ul><li><a href="/wiki/Computer_science" title="Computer science">Computer science</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Manual_of_Style/Infoboxes" title="Wikipedia:Manual of Style/Infoboxes">Infobox</a></i> :</b> <div> <ul><li><a href="/wiki/Category:Computer_science_articles_without_infoboxes" title="Category:Computer science articles without infoboxes">Computer science articles without infoboxes</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Maintenance" title="Wikipedia:Maintenance">Maintain</a></i> :</b> <div> <ul><li><a href="/wiki/Timeline_of_computing_2020%E2%80%93present" title="Timeline of computing 2020–present">Timeline of computing 2020–present</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Requested_pictures" title="Wikipedia:Requested pictures">Photo</a></i> :</b> <div> <ul><li>Find pictures for the biographies of computer scientists (see <a href="/wiki/List_of_computer_scientists" title="List of computer scientists">List of computer scientists</a>)</li> <li><a href="/wiki/Category:Computing_articles_needing_images" title="Category:Computing articles needing images">Computing articles needing images</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Stub" title="Wikipedia:Stub">Stubs</a></i> :</b> <div> <ul><li><a href="/wiki/Category:Computer_science_stubs" title="Category:Computer science stubs">Computer science stubs</a></li></ul> </div></li><li><b><i><a href="/wiki/Wikipedia:Reliable_sources" title="Wikipedia:Reliable sources">Unreferenced</a></i> :</b> <div> <ul><li><a href="/wiki/Wikipedia:WikiProject_Computer_science/Unreferenced_BLPs" title="Wikipedia:WikiProject Computer science/Unreferenced BLPs">WikiProject Computer science/Unreferenced BLPs</a></li></ul> </div></li><li><b><i>Project-related</i> :</b> <div> <ul><li>Tag all relevant articles in <a href="/wiki/Category:Computer_science" title="Category:Computer science">Category:Computer science</a> and sub-categories with <span class="nowrap">{{</span><a href="/wiki/Template:WikiProject_Computer_science" title="Template:WikiProject Computer science">WikiProject Computer science</a><span class="nowrap">}}</span></li></ul> </div></li> </ul> </div> </td></tr></tbody></table></td></tr></tbody></table></td></tr></tbody></table></td></tr></tbody></table></td></tr></tbody></table> <p><br> </p> <div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none"><div class="toctitle" lang="en" dir="ltr"><h2 id="mw-toc-heading">Contents</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div> <ul> <li class="toclevel-1 tocsection-1"><a href="#Untitled"><span class="tocnumber">1</span> <span class="toctext">Untitled</span></a></li> <li class="toclevel-1 tocsection-2"><a href="#P=NP_or_P=BPP?"><span class="tocnumber">2</span> <span class="toctext">P=NP or P=BPP?</span></a></li> <li class="toclevel-1 tocsection-3"><a href="#BPP_and_P_terminology/linguistics"><span class="tocnumber">3</span> <span class="toctext">BPP and P terminology/linguistics</span></a></li> <li class="toclevel-1 tocsection-4"><a href="#BPP_and_Monte_Carlo"><span class="tocnumber">4</span> <span class="toctext">BPP and Monte Carlo</span></a></li> <li class="toclevel-1 tocsection-5"><a href="#Bounds"><span class="tocnumber">5</span> <span class="toctext">Bounds</span></a></li> <li class="toclevel-1 tocsection-6"><a href="#k_runs"><span class="tocnumber">6</span> <span class="toctext">k runs</span></a></li> </ul> </div> </section><div class="mw-heading mw-heading2 ext-discussiontools-init-section section-heading" onclick="mfTempOpenSection(1)"><span class="indicator mf-icon mf-icon-expand mf-icon--small"></span><h2 id="Untitled" data-mw-thread-id="h-Untitled-2005-12-03T19:29:00.000Z"><span data-mw-comment-start="" id="h-Untitled-2005-12-03T19:29:00.000Z"></span>Untitled<span data-mw-comment-end="h-Untitled-2005-12-03T19:29:00.000Z"></span></h2><span class="mw-editsection"> <a role="button" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=1" title="Edit section: Untitled" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet "> <span class="minerva-icon minerva-icon--edit"></span> <span>edit</span> </a> </span> <span id='ooui-php-23' class='ext-discussiontools-init-section-overflowMenuButton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonMenuSelectWidget","rel":["nofollow"],"framed":false,"icon":"ellipsis","data":{"itemConfigs":[{"id":"edit","data":{"id":"edit"},"icon":"edit","label":"Edit"}],"resourceLoaderModules":[]},"classes":["ext-discussiontools-init-section-overflowMenuButton"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-ellipsis'></span><span class='oo-ui-labelElement-label'></span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-timestampLabel'>Latest comment: <a href="#c-Deco-2005-12-03T19:29:00.000Z-Untitled">18 years ago</a></span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-commentCountLabel'>1 comment</span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-authorCountLabel'>1 person in discussion</span></div><div class="ext-discussiontools-init-section-actions"></div></div></div><section class="mf-section-1 collapsible-block" id="mf-section-1"> <p><span data-mw-comment-start="" id="c-Deco-2005-12-03T19:29:00.000Z-Untitled"></span>Some examples of BPP / BPP-complete problems might be appreciated </p><p><br> What does this 1/4-clause mean in long run ? That chance of failure in many runs is (1/4)^N, 1/2*(1/2)^N or what ? --<a href="/wiki/User:Taw" title="User:Taw">Taw</a> </p> <dl><dd>The idea is that running it <i>n</i> times and choosing the answer that occurred most often (a "majority vote") will almost always be correct for relative small <i>n</i> (like say, 20-50). The calculations aren't quite as simple as you describe, but are a consequence of the <a href="/wiki/Chernoff_bound" title="Chernoff bound">Chernoff bound</a>. <a href="/wiki/User:Dcoetzee" title="User:Dcoetzee">Deco</a> 10:31, 24 Mar 2005 (UTC)</dd></dl> <hr> <p>I'm not familiar with Wikipedia customs, and English is not my mother tongue, so I may not express myself clearly enough, but let me ask a question to all the editors of this page: Those who don't understand computational complexity theory why don't just shut up here? I quote: "The existence of certain strong Pseudorandom number generators imply that P=RP=BPP. This implication is conjectured to be true." </p><p>Jesus. The implication is true, it is not a conjecture, it is a theorem by Nisan and Wigderson. The existence of those generators is the conjecture, which depends on certain hardness assumptions. There are several such results, I think the latest and strongest is by Impagliazzo and Wigderson from 1997, who prove that P=BPP if E contains a language which has 2^Omega(n) circuit complexity for almost every n. </p><p>This even got a corrected version: "It has been conjectured that the existence of certain strong pseudorandom number generators implies that P=RP=BPP." Just as stupid as the previous one. </p><p>Let me politely ask everyone here not to edit this page if he/she doesn't have a clue about the subject. </p> <dl><dd>Please, <a href="/wiki/Wikipedia:No_personal_attacks" title="Wikipedia:No personal attacks">no personal attacks</a>. Your change is correct to my knowledge, and we appreciate the help. The original editor's knowledge may have been out-of-date, since this is not a classical result, or it may have been referring to some stronger result based on a stronger definition. I'm not really sure what happened, but even experts make incorrect statements in their area. <a href="/wiki/User:Dcoetzee" title="User:Dcoetzee">Deco</a> 04:47, 4 Jan 2005 (UTC)</dd></dl> <p>The above commenter may know one thing about complexity theory, but does not know anything about manners. He/she definitely does not represent the complexity theory community, which I know to mostly contain very nice and respectful people. --Boaz, March 21, 2005. </p> <hr> <p>Hmm. There is some subtle difference between P and BPP. Example: Let we have probabilistic algorithm for adding two binary numbers of length n. This algorithm uses rnd() somewhere. On non-deterministic turing machine, this algorithm will have probability of success A , that can be made close to 1 by computing it many times (it is never 1 , but with some luck i can expect to get correct results). </p><p>On deterministic turing machine, one has to use pseudorandom number generator always seeded with same value(otherwise algorithm isn't deterministic), and this algorithm will fail for some inputs. Thus it is not an universal algorithm for adding binary numbers. The difference is subtle, but it is there. It has nothing to do with complexities, it's purely linguistical; it's just that P algorithm for addition of binary numbers does solve one problem (for pair of binary numbers, compute sum), and "BPP" algorithm using pseudorandom numbers solves other problems (for SOME pairs of binary numbers, give out sum, for some pairs, give out garbage) </p><p>So: If there is no algorithm that solves certain problem A in polynomial time, there could quite well be BPP algorithm for doing same thing _sometimes_(sometimes it will solve and sometimes it will fail)in polynomial time. And using strong pseudorandom number generator, there will be deterministic polynomial time algorithm for solving this problem for some inputs. But generally speaking, this algorithm will not be the solution to original problem A, because it will only work for some inputs. </p><p>My point is that "there is P algorithm to some problem A" and "there is BPP algorithm for some problem A" mean different things and you can not use pseudorandom number generator to turn latter into former (you will get "P algorithm that solves A for some restricted set of inputs and gives out garbage for other set") </p><p>--DL , December 03, 2005. </p> <dl><dd>You are correct that ordinary pseudorandom number generators cannot (as far as we know) be used to produce polynomial-time algorithms based on BPP algorithms; instead, a source of "true" randomness is required. It <i>has</i> been proven that some probabilistic algorithms can solve a problem in polynomial time given only a small number of random bits, just enough for a "seed". It is an open question in research whether P=BPP, and research in this direction has generally followed the idea of producing pseudorandom generators sophisticated enough to actually replace truly random bits in certain applications. But to claim as a matter of fact that P≠BPP is really jumping the gun - there's convincing evidence to the contrary. <a href="/w/index.php?title=User:Deco&action=edit&redlink=1" class="new" title="User:Deco (page does not exist)">Deco</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Deco-2005-12-03T19:29:00.000Z-Untitled" class="ext-discussiontools-init-timestamplink">19:29, 3 December 2005 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Deco-2005-12-03T19:29:00.000Z-Untitled"><span id="ooui-php-1" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Deco-2005-12-03T19:29:00.000Z-Untitled"></span> <dl><dd>I think you have not read what I wrote well enough. Issue has nothing to do with strength of pseudorandom numbers(longer explanation on bottom of page). Yes, with strong pseudorandom numbers you can emulate non-deterministic machine, and for sake of this talk i can assume that you emulate it perfectly. But it only let you turns what we name "BPP solutuion to problem A" into what is named "P solution for problem A that gives out garbage for certain inputs", and latter is NOT equivalent to "P solution for problem A [it is implied that it'll work for all inputs]". It's classic example of English terminology being not accurate enough to clearly specify the difference between "being able to emulate BPP on deterministic machine", and "BPP solution to problem A" being equivalent to "P solution to problem A". I agree with you that with strong pseudorandom number generator you can run BPP algorithms on deterministic machine. But it is not related to what i argue about.</dd></dl></dd></dl> </section><div class="mw-heading mw-heading2 ext-discussiontools-init-section section-heading" onclick="mfTempOpenSection(2)"><span class="indicator mf-icon mf-icon-expand mf-icon--small"></span><h2 id="P=NP_or_P=BPP?" data-mw-thread-id="h-P=NP_or_P=BPP?-2005-12-03T19:37:00.000Z"><span id="P.3DNP_or_P.3DBPP.3F"></span><span data-mw-comment-start="" id="h-P=NP_or_P=BPP?-2005-12-03T19:37:00.000Z"></span>P=NP or P=BPP?<span data-mw-comment-end="h-P=NP_or_P=BPP?-2005-12-03T19:37:00.000Z"></span></h2><span class="mw-editsection"> <a role="button" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=2" title="Edit section: P=NP or P=BPP?" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet "> <span class="minerva-icon minerva-icon--edit"></span> <span>edit</span> </a> </span> <span id='ooui-php-24' class='ext-discussiontools-init-section-overflowMenuButton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonMenuSelectWidget","rel":["nofollow"],"framed":false,"icon":"ellipsis","data":{"itemConfigs":[{"id":"edit","data":{"id":"edit"},"icon":"edit","label":"Edit"}],"resourceLoaderModules":[]},"classes":["ext-discussiontools-init-section-overflowMenuButton"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-ellipsis'></span><span class='oo-ui-labelElement-label'></span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-timestampLabel'>Latest comment: <a href="#c-MarkSweep-2005-12-04T18:18:00.000Z-Deco-2005-12-03T19:37:00.000Z">18 years ago</a></span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-commentCountLabel'>2 comments</span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-authorCountLabel'>2 people in discussion</span></div><div class="ext-discussiontools-init-section-actions"></div></div></div><section class="mf-section-2 collapsible-block" id="mf-section-2"> <p><span data-mw-comment-start="" id="c-Deco-2005-12-03T19:37:00.000Z-P=NP_or_P=BPP?"></span>Is it really true that one of P=NP or P=BPP is true? I find this a bit hard to believe. Who added this claim (regarding exponential size circuits for EXPTIME) and where's your reference? Thanks. <a href="/w/index.php?title=User:Deco&action=edit&redlink=1" class="new" title="User:Deco (page does not exist)">Deco</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Deco-2005-12-03T19:37:00.000Z-P=NP_or_P=BPP?" class="ext-discussiontools-init-timestamplink">19:37, 3 December 2005 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Deco-2005-12-03T19:37:00.000Z-P=NP_or_P=BPP?"><span id="ooui-php-2" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Deco-2005-12-03T19:37:00.000Z-P=NP_or_P=BPP?"></span> </p> <dl><dd><span data-mw-comment-start="" id="c-MarkSweep-2005-12-04T18:18:00.000Z-Deco-2005-12-03T19:37:00.000Z"></span>I've commented out that paragraph, since it's most likley wrong. P=NP would imply P=BPP, so the disjunction (P=NP or P=BPP) would in turn imply P=BPP unconditionally. This is not known to be the case. --<a href="/wiki/User:MarkSweep" title="User:MarkSweep">MarkSweep</a> <small><a href="/wiki/User_talk:MarkSweep" title="User talk:MarkSweep">(call me collect)</a></small> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-MarkSweep-2005-12-04T18:18:00.000Z-Deco-2005-12-03T19:37:00.000Z" class="ext-discussiontools-init-timestamplink">18:18, 4 December 2005 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-MarkSweep-2005-12-04T18:18:00.000Z-Deco-2005-12-03T19:37:00.000Z"><span id="ooui-php-3" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-MarkSweep-2005-12-04T18:18:00.000Z-Deco-2005-12-03T19:37:00.000Z"></span></dd></dl> </section><div class="mw-heading mw-heading2 ext-discussiontools-init-section section-heading" onclick="mfTempOpenSection(3)"><span class="indicator mf-icon mf-icon-expand mf-icon--small"></span><h2 id="BPP_and_P_terminology/linguistics" data-mw-thread-id="h-BPP_and_P_terminology/linguistics-2005-12-04T18:36:00.000Z"><span id="BPP_and_P_terminology.2Flinguistics"></span><span data-mw-comment-start="" id="h-BPP_and_P_terminology/linguistics-2005-12-04T18:36:00.000Z"></span>BPP and P terminology/linguistics<span data-mw-comment-end="h-BPP_and_P_terminology/linguistics-2005-12-04T18:36:00.000Z"></span></h2><span class="mw-editsection"> <a role="button" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=3" title="Edit section: BPP and P terminology/linguistics" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet "> <span class="minerva-icon minerva-icon--edit"></span> <span>edit</span> </a> </span> <span id='ooui-php-25' class='ext-discussiontools-init-section-overflowMenuButton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonMenuSelectWidget","rel":["nofollow"],"framed":false,"icon":"ellipsis","data":{"itemConfigs":[{"id":"edit","data":{"id":"edit"},"icon":"edit","label":"Edit"}],"resourceLoaderModules":[]},"classes":["ext-discussiontools-init-section-overflowMenuButton"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-ellipsis'></span><span class='oo-ui-labelElement-label'></span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-timestampLabel'>Latest comment: <a href="#c-EmilJ-2010-07-15T10:08:00.000Z-JumpDiscont-2010-07-14T20:20:00.000Z">14 years ago</a></span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-commentCountLabel'>7 comments</span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-authorCountLabel'>5 people in discussion</span></div><div class="ext-discussiontools-init-section-actions"></div></div></div><section class="mf-section-3 collapsible-block" id="mf-section-3"> <p><span data-mw-comment-start="" id="c-MarkSweep-2005-12-04T18:36:00.000Z-BPP_and_P_terminology/linguistics"></span>My point is that: </p><p>Let I have developed "BPP algorithm for adding two binary numbers", and "P algorithm for adding two binary numbers" (i.e. both algorithms works in polynomial time but former fails with probability 1/3). Them are in fact solving two different problems: </p><p>"BPP algorithm" solves the problem SOMETIMES, and "P algorithm" solves it ALWAYS. </p><p>On deterministic machine, result depends soliely to input. If you "convert" BPP to P using pseudorandom number generator, no matter how strong, you will get "P algorithm that gives out sum for SOME pairs of binary numbers (and for some it gives garbage)". (unless you believe that with your pseudorandom number genrator it will work way better than it worked with true random numbers :-) ) </p><p>So, there is "P algorithm that gives sum for ANY pair of binary numbers", and "P algorithm that gives sum for SOME pairs of binary numbers (and garbage for other pairs)". </p><p>It is clear that these two algorithms are solving _different_ problems. It has precisely nothing to do with strength of pseudorandom number generator, as long as it is deterministic. </p><p>You could even use "ultimately strong" (pseudo?)random number source, such as file with data obtained from true random number generator. (we can say that this file is part of algorithm :-) It's as close to true randomness as you can get on deterministic machine (even to the point that some people would argue it isn't deterministic :-) ). But the _only_ property i use is that with same seed it gives same sequence, so my argumentation will work regardless of strength of random number generator, or even with true random numbers if them is written to file for repeatability. </p><p>If you are thinking about using different seeds and "inheriting" seed from previous run like how you do that in software, then you get "P algorithm that takes seed and pair of binary numbers, and for some parameters gives out sum of binary numbers (for other, garbage), and the final random seed" (It's not original problem at all.) </p><p>In summary, my point is: If we say that "there is BPP solution to problem A" it doesn't imply that we can say "there is P solution to problem A". However, with strong pseudorandom numbers, we can run same BPP algorithm on deterministic machine and get P solution to problem A that gives correct result for SOME inputs, and garbage for other. But it's not what we can name "P solution to problem A" because this BPP-like solution would give garbage for other inputs. If number of possible inputs is infinite, no matter from how many trials you compute majority vote, there will be some inputs when this algorithm will give out garbage. </p><p>Anyway, it absolutely doesn't matter what I think on subject and what logical reasoning i do have. If there is no references to research where it is shown that "existence of strong pseudorandom number generaturs implies BPP=P", or that "NP=P or BPP=P", these claims is "original insight", and it's way worse than "original research". Or maybe these claims is really trivial(i don't think it is the case), then whoever inserted them must provide proof. Sure, if it's so trivial that it doesn't need reference he shouldn't have problems proving it in few lines. </p><p>My point is related to terminology and linguistics. The problem is that when we say that "problem is BPP" and when we say "problem is P" it has different meanings regardless of random number generators. It is related to the human language. I actually agree that (most likely) problems that are in BPP are in "P that is allowed to fail for some inputs". </p><p>--DL , December 04, 2005. (will register soon.) </p> <dl><dd>I'm not sure I begin to understand your objection, but this won't stop me from trying to say something: Don't confuse problems with algorithms. Take a problem such as SATISFIABILITY: it asks whether a given propositional formula has a satisfying truth assignment. Now we can build several algorithms which work on this problem. Some of them will always return the correct answer while potentially taking a very long time. Some of them will return the correct answer most of the time while never requiring an unreasonable amount of time. Some of them will almost never return the correct answer, but will be blazingly fast.</dd></dl> <dl><dd>The class BPP is a class of <i>problems</i>. It consists of those problems for which algorithms exist which, loosely speaking, produce the correct solution more often than not, and in reasonable time. So a direct way of showing that a given problem is in BPP is to exhibit a polynomial-time algorithm with a better-than-average chance of obtaining the correct answer.</dd></dl> <dl><dd>As discussed above, a key issue is to quantify the computational advantage provided by a truly random source over a deterministically generated pseudorandom sequence. One way of proving P=BPP would be to show that there exist strong pseudorandom number generators that cannot be distinguished from a truly random source by an algorithm that is constrained to run in a certain amount of time. --<a href="/wiki/User:MarkSweep" title="User:MarkSweep">MarkSweep</a> <small><a href="/wiki/User_talk:MarkSweep" title="User talk:MarkSweep">(call me collect)</a></small> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-MarkSweep-2005-12-04T18:36:00.000Z-BPP_and_P_terminology/linguistics" class="ext-discussiontools-init-timestamplink">18:36, 4 December 2005 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-MarkSweep-2005-12-04T18:36:00.000Z-BPP_and_P_terminology/linguistics"><span id="ooui-php-4" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-MarkSweep-2005-12-04T18:36:00.000Z-BPP_and_P_terminology/linguistics"></span></dd></dl> <dl><dd><span data-mw-comment-start="" id="c-Deco-2005-12-04T19:25:00.000Z-MarkSweep-2005-12-04T18:36:00.000Z"></span>Okay, say we define a class ErrorP of problems such that some instances can be solved correctly in polynomial time, while other instances are solved incorrectly. In this case, your argument does clearly verify that BPP is contained in ErrorP. Unfortunately, this isn't very useful, because just about <i>every</i> problem is in ErrorP (just hard code the answer to one instance and return <i>no</i> for the rest). You can try to specify that it's only rarely wrong, but if you choose an arbitrary random number generator, it may so happen that you choose one that happens to get many instances wrong, perhaps almost all instances.</dd> <dd>Related is the idea of universal hashing, which says that, with high probability, any hash function from a class of functions is unlikely to produce long chains on random inputs. If one doesn't work, we can change to another and hope it works. Simple linear congruential random number generators are an example of such a class. But I don't know of any way to ensure that you will get a hash function that won't produce long chains or to show that this is unlikely if you choose a generator at random. <a href="/w/index.php?title=User:Deco&action=edit&redlink=1" class="new" title="User:Deco (page does not exist)">Deco</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Deco-2005-12-04T19:25:00.000Z-MarkSweep-2005-12-04T18:36:00.000Z" class="ext-discussiontools-init-timestamplink">19:25, 4 December 2005 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Deco-2005-12-04T19:25:00.000Z-MarkSweep-2005-12-04T18:36:00.000Z"><span id="ooui-php-5" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Deco-2005-12-04T19:25:00.000Z-MarkSweep-2005-12-04T18:36:00.000Z"></span></dd></dl> <dl><dd><dl><dd><span data-mw-comment-start="" id="c-Ben_Standeven-2006-03-24T00:43:00.000Z-Deco-2005-12-04T19:25:00.000Z"></span>The trick to showing that P = BPP is that, while any one seed may fail for certain inputs, a "good" random number generator will work for any input, <i>given the correct seed</i>. Then it's just a matter of looping over all possible seeds, which can be done in polynomial time, provided the required seed size is at most logarithmic in the problem size. <a href="/wiki/User:Ben_Standeven" title="User:Ben Standeven">Ben Standeven</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Ben_Standeven-2006-03-24T00:43:00.000Z-Deco-2005-12-04T19:25:00.000Z" class="ext-discussiontools-init-timestamplink">00:43, 24 March 2006 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Ben_Standeven-2006-03-24T00:43:00.000Z-Deco-2005-12-04T19:25:00.000Z"><span id="ooui-php-6" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Ben_Standeven-2006-03-24T00:43:00.000Z-Deco-2005-12-04T19:25:00.000Z"></span></dd></dl></dd></dl> <dl><dd><dl><dd><dl><dd><span data-mw-comment-start="" id="c-JumpDiscont-2010-07-13T20:15:00.000Z-Ben_Standeven-2006-03-24T00:43:00.000Z"></span>That would only work for P = RP. To show P = BPP, you need to be able to decide that a particular seed was one of the correct seeds.</dd> <dd><a href="/w/index.php?title=User:JumpDiscont&action=edit&redlink=1" class="new" title="User:JumpDiscont (page does not exist)">JumpDiscont</a> (<a href="/wiki/User_talk:JumpDiscont" title="User talk:JumpDiscont">talk</a>) <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-JumpDiscont-2010-07-13T20:15:00.000Z-Ben_Standeven-2006-03-24T00:43:00.000Z" class="ext-discussiontools-init-timestamplink">20:15, 13 July 2010 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-JumpDiscont-2010-07-13T20:15:00.000Z-Ben_Standeven-2006-03-24T00:43:00.000Z"><span id="ooui-php-7" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-JumpDiscont-2010-07-13T20:15:00.000Z-Ben_Standeven-2006-03-24T00:43:00.000Z"></span> <dl><dd><span data-mw-comment-start="" id="c-EmilJ-2010-07-14T11:42:00.000Z-JumpDiscont-2010-07-13T20:15:00.000Z"></span>Most seeds are correct. You are supposed to loop over all possible seeds, and (for BPP) take a majority vote among the answers received.—<a href="/wiki/User:EmilJ" title="User:EmilJ">Emil</a> <a href="/wiki/User_talk:EmilJ" title="User talk:EmilJ">J.</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-EmilJ-2010-07-14T11:42:00.000Z-JumpDiscont-2010-07-13T20:15:00.000Z" class="ext-discussiontools-init-timestamplink">11:42, 14 July 2010 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-EmilJ-2010-07-14T11:42:00.000Z-JumpDiscont-2010-07-13T20:15:00.000Z"><span id="ooui-php-8" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-EmilJ-2010-07-14T11:42:00.000Z-JumpDiscont-2010-07-13T20:15:00.000Z"></span></dd></dl></dd></dl></dd></dl></dd></dl> <dl><dd><dl><dd><dl><dd><dl><dd><dl><dd><span data-mw-comment-start="" id="c-JumpDiscont-2010-07-14T20:20:00.000Z-EmilJ-2010-07-14T11:42:00.000Z"></span>Is your idea that it _should_ be easy to show that most seeds are correct, or that someone has already shown that for some specific (hopefully nonempty) class of prngs, most seeds are correct?</dd> <dd><a href="/w/index.php?title=User:JumpDiscont&action=edit&redlink=1" class="new" title="User:JumpDiscont (page does not exist)">JumpDiscont</a> (<a href="/wiki/User_talk:JumpDiscont" title="User talk:JumpDiscont">talk</a>) <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-JumpDiscont-2010-07-14T20:20:00.000Z-EmilJ-2010-07-14T11:42:00.000Z" class="ext-discussiontools-init-timestamplink">20:20, 14 July 2010 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-JumpDiscont-2010-07-14T20:20:00.000Z-EmilJ-2010-07-14T11:42:00.000Z"><span id="ooui-php-9" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-JumpDiscont-2010-07-14T20:20:00.000Z-EmilJ-2010-07-14T11:42:00.000Z"></span> <dl><dd><span data-mw-comment-start="" id="c-EmilJ-2010-07-15T10:08:00.000Z-JumpDiscont-2010-07-14T20:20:00.000Z"></span>It's not my idea, it's the <i>definition</i> of a pseudorandom generator. See e.g. the classical Nisan–Wigderson paper<a rel="nofollow" class="external autonumber" href="http://www.cs.huji.ac.il/~noam/hard.ps">[1]</a>.—<a href="/wiki/User:EmilJ" title="User:EmilJ">Emil</a> <a href="/wiki/User_talk:EmilJ" title="User talk:EmilJ">J.</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-EmilJ-2010-07-15T10:08:00.000Z-JumpDiscont-2010-07-14T20:20:00.000Z" class="ext-discussiontools-init-timestamplink">10:08, 15 July 2010 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-EmilJ-2010-07-15T10:08:00.000Z-JumpDiscont-2010-07-14T20:20:00.000Z"><span id="ooui-php-10" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-EmilJ-2010-07-15T10:08:00.000Z-JumpDiscont-2010-07-14T20:20:00.000Z"></span></dd></dl></dd></dl></dd></dl></dd></dl></dd></dl></dd></dl> </section><div class="mw-heading mw-heading2 ext-discussiontools-init-section section-heading" onclick="mfTempOpenSection(4)"><span class="indicator mf-icon mf-icon-expand mf-icon--small"></span><h2 id="BPP_and_Monte_Carlo" data-mw-thread-id="h-BPP_and_Monte_Carlo-2006-03-27T20:18:00.000Z"><span data-mw-comment-start="" id="h-BPP_and_Monte_Carlo-2006-03-27T20:18:00.000Z"></span>BPP and Monte Carlo<span data-mw-comment-end="h-BPP_and_Monte_Carlo-2006-03-27T20:18:00.000Z"></span></h2><span class="mw-editsection"> <a role="button" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=4" title="Edit section: BPP and Monte Carlo" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet "> <span class="minerva-icon minerva-icon--edit"></span> <span>edit</span> </a> </span> <span id='ooui-php-26' class='ext-discussiontools-init-section-overflowMenuButton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonMenuSelectWidget","rel":["nofollow"],"framed":false,"icon":"ellipsis","data":{"itemConfigs":[{"id":"edit","data":{"id":"edit"},"icon":"edit","label":"Edit"}],"resourceLoaderModules":[]},"classes":["ext-discussiontools-init-section-overflowMenuButton"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-ellipsis'></span><span class='oo-ui-labelElement-label'></span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-timestampLabel'>Latest comment: <a href="#c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo">17 years ago</a></span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-commentCountLabel'>5 comments</span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-authorCountLabel'>3 people in discussion</span></div><div class="ext-discussiontools-init-section-actions"></div></div></div><section class="mf-section-4 collapsible-block" id="mf-section-4"> <p><span data-mw-comment-start="" id="c-Ozga-2006-03-27T20:18:00.000Z-BPP_and_Monte_Carlo"></span>Is BPP equivalent to Monte Carlo? We have elsewhere ZPP is equivalent to Las Vegas. -<a href="/w/index.php?title=User:Ozga&action=edit&redlink=1" class="new" title="User:Ozga (page does not exist)">Ozga</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Ozga-2006-03-27T20:18:00.000Z-BPP_and_Monte_Carlo" class="ext-discussiontools-init-timestamplink">20:18, 27 March 2006 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Ozga-2006-03-27T20:18:00.000Z-BPP_and_Monte_Carlo"><span id="ooui-php-11" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Ozga-2006-03-27T20:18:00.000Z-BPP_and_Monte_Carlo"></span> </p> <dl><dd><span data-mw-comment-start="" id="c-EJ-2006-03-27T22:39:00.000Z-Ozga-2006-03-27T20:18:00.000Z"></span>Yes, BPP-algorithms are equivalent to one of those casino towns. -- <a href="/wiki/User:EJ" class="mw-redirect" title="User:EJ">EJ</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-EJ-2006-03-27T22:39:00.000Z-Ozga-2006-03-27T20:18:00.000Z" class="ext-discussiontools-init-timestamplink">22:39, 27 March 2006 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-EJ-2006-03-27T22:39:00.000Z-Ozga-2006-03-27T20:18:00.000Z"><span id="ooui-php-12" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-EJ-2006-03-27T22:39:00.000Z-Ozga-2006-03-27T20:18:00.000Z"></span></dd></dl> <p><span data-mw-comment-start="" id="c-Ozga-2006-03-28T05:36:00.000Z-BPP_and_Monte_Carlo"></span>Would it be a good thing to mention this in the article? I think so. -- <a href="/w/index.php?title=User:Ozga&action=edit&redlink=1" class="new" title="User:Ozga (page does not exist)">Ozga</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Ozga-2006-03-28T05:36:00.000Z-BPP_and_Monte_Carlo" class="ext-discussiontools-init-timestamplink">05:36, 28 March 2006 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Ozga-2006-03-28T05:36:00.000Z-BPP_and_Monte_Carlo"><span id="ooui-php-13" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Ozga-2006-03-28T05:36:00.000Z-BPP_and_Monte_Carlo"></span> </p><p><span data-mw-comment-start="" id="c-Ozga-2006-03-30T17:06:00.000Z-BPP_and_Monte_Carlo"></span>Papdimitriou defines Monte Carlo as equivalent to RP. Hmm. <a href="/w/index.php?title=User:Ozga&action=edit&redlink=1" class="new" title="User:Ozga (page does not exist)">Ozga</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Ozga-2006-03-30T17:06:00.000Z-BPP_and_Monte_Carlo" class="ext-discussiontools-init-timestamplink">17:06, 30 March 2006 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Ozga-2006-03-30T17:06:00.000Z-BPP_and_Monte_Carlo"><span id="ooui-php-14" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Ozga-2006-03-30T17:06:00.000Z-BPP_and_Monte_Carlo"></span> </p><p><span data-mw-comment-start="" id="c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo"></span>BPP is referred to as "Atlantic City," not Monte Carlo or Las Vegas. <a href="/w/index.php?title=User:Sadeq&action=edit&redlink=1" class="new" title="User:Sadeq (page does not exist)">Sadeq</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo" class="ext-discussiontools-init-timestamplink">04:44, 17 August 2007 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo"><span id="ooui-php-15" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo"></span> </p> </section><div class="mw-heading mw-heading2 ext-discussiontools-init-section section-heading" onclick="mfTempOpenSection(5)"><span class="indicator mf-icon mf-icon-expand mf-icon--small"></span><h2 id="Bounds" data-mw-thread-id="h-Bounds-2009-11-11T19:07:00.000Z"><span data-mw-comment-start="" id="h-Bounds-2009-11-11T19:07:00.000Z"></span>Bounds<span data-mw-comment-end="h-Bounds-2009-11-11T19:07:00.000Z"></span></h2><span class="mw-editsection"> <a role="button" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=5" title="Edit section: Bounds" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet "> <span class="minerva-icon minerva-icon--edit"></span> <span>edit</span> </a> </span> <span id='ooui-php-27' class='ext-discussiontools-init-section-overflowMenuButton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonMenuSelectWidget","rel":["nofollow"],"framed":false,"icon":"ellipsis","data":{"itemConfigs":[{"id":"edit","data":{"id":"edit"},"icon":"edit","label":"Edit"}],"resourceLoaderModules":[]},"classes":["ext-discussiontools-init-section-overflowMenuButton"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-ellipsis'></span><span class='oo-ui-labelElement-label'></span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-timestampLabel'>Latest comment: <a href="#c-EmilJ-2009-11-12T13:20:00.000Z-RobinK-2009-11-12T13:01:00.000Z">15 years ago</a></span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-commentCountLabel'>5 comments</span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-authorCountLabel'>2 people in discussion</span></div><div class="ext-discussiontools-init-section-actions"></div></div></div><section class="mf-section-5 collapsible-block" id="mf-section-5"> <p><span data-mw-comment-start="" id="c-EmilJ-2009-11-11T19:07:00.000Z-Bounds"></span>The bound <i>e</i><sup>−<i>k</i>/18</sup> on the error for <i>k</i> runs is suboptimal, it seems to be an artifact of whatever general version of Chernoff's bound was used to derive it. The actual value is of the order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {k}}}\left({\frac {2{\sqrt {2}}}{3}}\right)^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mi>k</mi> </msqrt> </mfrac> </mrow> <msup> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> </msqrt> </mrow> </mrow> <mn>3</mn> </mfrac> </mrow> <mo>)</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {k}}}\left({\frac {2{\sqrt {2}}}{3}}\right)^{k}}</annotation> </semantics> </math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3b7f73ca5321a6de80fa8535d0c1b7054953d9f7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:13.59ex; height:7.343ex;" alt="{\displaystyle {\frac {1}{\sqrt {k}}}\left({\frac {2{\sqrt {2}}}{3}}\right)^{k}}"></noscript><span class="lazy-image-placeholder" style="width: 13.59ex;height: 7.343ex;vertical-align: -2.838ex;" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3b7f73ca5321a6de80fa8535d0c1b7054953d9f7" data-alt="{\displaystyle {\frac {1}{\sqrt {k}}}\left({\frac {2{\sqrt {2}}}{3}}\right)^{k}}" data-class="mwe-math-fallback-image-inline mw-invert skin-invert"> </span></span>, which is about <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{-k/16.98}\,}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>16.98</mn> </mrow> </msup> <mspace width="thinmathspace"></mspace> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle e^{-k/16.98}\,}</annotation> </semantics> </math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0112fc1e6bcb411c754643a9f37f9b708c3eecea" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.405ex; height:2.843ex;" alt="{\displaystyle e^{-k/16.98}\,}"></noscript><span class="lazy-image-placeholder" style="width: 8.405ex;height: 2.843ex;vertical-align: -0.338ex;" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0112fc1e6bcb411c754643a9f37f9b708c3eecea" data-alt="{\displaystyle e^{-k/16.98}\,}" data-class="mwe-math-fallback-image-inline mw-invert skin-invert"> </span></span>. It does not make any practical difference (especially since the convention of using 1/3 for the error of one run is itself completely arbitrary), but still I think that it is a bit misleading to give arbitrary numbers in the table which make a false impression of being tight. — <a href="/wiki/User:EmilJ" title="User:EmilJ">Emil</a> <a href="/wiki/User_talk:EmilJ" title="User talk:EmilJ">J.</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-EmilJ-2009-11-11T19:07:00.000Z-Bounds" class="ext-discussiontools-init-timestamplink">19:07, 11 November 2009 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-EmilJ-2009-11-11T19:07:00.000Z-Bounds"><span id="ooui-php-16" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-EmilJ-2009-11-11T19:07:00.000Z-Bounds"></span> </p> <dl><dd><span data-mw-comment-start="" id="c-RobinK-2009-11-11T22:00:00.000Z-EmilJ-2009-11-11T19:07:00.000Z"></span>I agree. What do you suggest? Putting in the value "16.98" also seems pretty pointless. --<a href="/wiki/User:RobinK" title="User:RobinK">Robin</a> (<a href="/wiki/User_talk:RobinK" title="User talk:RobinK">talk</a>) <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-RobinK-2009-11-11T22:00:00.000Z-EmilJ-2009-11-11T19:07:00.000Z" class="ext-discussiontools-init-timestamplink">22:00, 11 November 2009 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-RobinK-2009-11-11T22:00:00.000Z-EmilJ-2009-11-11T19:07:00.000Z"><span id="ooui-php-17" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-RobinK-2009-11-11T22:00:00.000Z-EmilJ-2009-11-11T19:07:00.000Z"></span> <dl><dd><span data-mw-comment-start="" id="c-EmilJ-2009-11-12T11:44:00.000Z-RobinK-2009-11-11T22:00:00.000Z"></span>I'm not quite sure what would be the best way to solve it. Maybe just say something like "2<sup>−<i>ck</i></sup> for some constant <i>c</i> > 0", and leave the exact value unspecified? — <a href="/wiki/User:EmilJ" title="User:EmilJ">Emil</a> <a href="/wiki/User_talk:EmilJ" title="User talk:EmilJ">J.</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-EmilJ-2009-11-12T11:44:00.000Z-RobinK-2009-11-11T22:00:00.000Z" class="ext-discussiontools-init-timestamplink">11:44, 12 November 2009 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-EmilJ-2009-11-12T11:44:00.000Z-RobinK-2009-11-11T22:00:00.000Z"><span id="ooui-php-18" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-EmilJ-2009-11-12T11:44:00.000Z-RobinK-2009-11-11T22:00:00.000Z"></span> <dl><dd><span data-mw-comment-start="" id="c-RobinK-2009-11-12T13:01:00.000Z-EmilJ-2009-11-12T11:44:00.000Z"></span>The phrase "for some constant <i>c</i> > 0" seems too long to put in the infobox. But I have no other ideas, so go ahead with this. Maybe someone will think of something better. --<a href="/wiki/User:RobinK" title="User:RobinK">Robin</a> (<a href="/wiki/User_talk:RobinK" title="User talk:RobinK">talk</a>) <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-RobinK-2009-11-12T13:01:00.000Z-EmilJ-2009-11-12T11:44:00.000Z" class="ext-discussiontools-init-timestamplink">13:01, 12 November 2009 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-RobinK-2009-11-12T13:01:00.000Z-EmilJ-2009-11-12T11:44:00.000Z"><span id="ooui-php-19" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-RobinK-2009-11-12T13:01:00.000Z-EmilJ-2009-11-12T11:44:00.000Z"></span> <dl><dd><span data-mw-comment-start="" id="c-EmilJ-2009-11-12T13:20:00.000Z-RobinK-2009-11-12T13:01:00.000Z"></span>OK, I've implemented the change. Feel free to fix it if you get a better idea. — <a href="/wiki/User:EmilJ" title="User:EmilJ">Emil</a> <a href="/wiki/User_talk:EmilJ" title="User talk:EmilJ">J.</a> <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-EmilJ-2009-11-12T13:20:00.000Z-RobinK-2009-11-12T13:01:00.000Z" class="ext-discussiontools-init-timestamplink">13:20, 12 November 2009 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-EmilJ-2009-11-12T13:20:00.000Z-RobinK-2009-11-12T13:01:00.000Z"><span id="ooui-php-20" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-EmilJ-2009-11-12T13:20:00.000Z-RobinK-2009-11-12T13:01:00.000Z"></span></dd></dl></dd></dl></dd></dl></dd></dl> </section><div class="mw-heading mw-heading2 ext-discussiontools-init-section section-heading" onclick="mfTempOpenSection(6)"><span class="indicator mf-icon mf-icon-expand mf-icon--small"></span><h2 id="k_runs" data-mw-thread-id="h-k_runs-20230125103300"><span data-mw-comment-start="" id="h-k_runs-20230125103300"></span>k runs<span data-mw-comment-end="h-k_runs-20230125103300"></span></h2><span class="mw-editsection"> <a role="button" href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=6" title="Edit section: k runs" class="cdx-button cdx-button--size-large cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--icon-only cdx-button--weight-quiet "> <span class="minerva-icon minerva-icon--edit"></span> <span>edit</span> </a> </span> <span id='ooui-php-28' class='ext-discussiontools-init-section-overflowMenuButton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonMenuSelectWidget","rel":["nofollow"],"framed":false,"icon":"ellipsis","data":{"itemConfigs":[{"id":"edit","data":{"id":"edit"},"icon":"edit","label":"Edit"}],"resourceLoaderModules":[]},"classes":["ext-discussiontools-init-section-overflowMenuButton"]}'><a role='button' tabindex='0' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-ellipsis'></span><span class='oo-ui-labelElement-label'></span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator'></span></a></span><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-timestampLabel'>Latest comment: <a href="#c-Bilorv-20230128134100-62.166.189.223-20230125103300">1 year ago</a></span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-commentCountLabel'>2 comments</span><span class='ext-discussiontools-init-section-metaitem ext-discussiontools-init-section-authorCountLabel'>2 people in discussion</span></div><div class="ext-discussiontools-init-section-actions"></div></div></div><section class="mf-section-6 collapsible-block" id="mf-section-6"> <p><span data-mw-comment-start="" id="c-62.166.189.223-20230125103300-k_runs"></span>In the table next to the intro/definition, I believe the 2^{-ck} error bounds for k runs are incorrect, because majority voting doesn't converge that fast. This should be 2^{-c*sqrt(k)} I believe. <a href="/wiki/Special:Contributions/62.166.189.223" title="Special:Contributions/62.166.189.223">62.166.189.223</a> (<a href="/w/index.php?title=User_talk:62.166.189.223&action=edit&redlink=1" class="new" title="User talk:62.166.189.223 (page does not exist)">talk</a>) <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-62.166.189.223-20230125103300-k_runs" class="ext-discussiontools-init-timestamplink">10:33, 25 January 2023 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-62.166.189.223-20230125103300-k_runs"><span id="ooui-php-21" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-62.166.189.223-20230125103300-k_runs"></span> </p> <dl><dd><span data-mw-comment-start="" id="c-Bilorv-20230128134100-62.166.189.223-20230125103300"></span>See the above section. I think the table is correct and this is the result you get from <a href="/wiki/Chernoff_bound" title="Chernoff bound">Chernoff bounds</a> or "probability amplification" or "majority voting" or whatever you want to call it. I did a search and saw a few different lecture notes that I think give equivalent results to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-ck}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>c</mi> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{-ck}}</annotation> </semantics> </math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c10a2d6d9cabf394b972d238e011abc9dc443de" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.242ex; height:2.676ex;" alt="{\displaystyle 2^{-ck}}"></noscript><span class="lazy-image-placeholder" style="width: 4.242ex;height: 2.676ex;vertical-align: -0.338ex;" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c10a2d6d9cabf394b972d238e011abc9dc443de" data-alt="{\displaystyle 2^{-ck}}" data-class="mwe-math-fallback-image-inline mw-invert skin-invert"> </span></span> e.g. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{-k/18}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>18</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle e^{-k/18}}</annotation> </semantics> </math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a6743332dea74f8db61e173767b496428e95dd9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.917ex; height:2.843ex;" alt="{\displaystyle e^{-k/18}}"></noscript><span class="lazy-image-placeholder" style="width: 5.917ex;height: 2.843ex;vertical-align: -0.338ex;" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5a6743332dea74f8db61e173767b496428e95dd9" data-alt="{\displaystyle e^{-k/18}}" data-class="mwe-math-fallback-image-inline mw-invert skin-invert"> </span></span>, depending on the precise Chernoff bound. — <a href="/wiki/User:Bilorv" title="User:Bilorv">Bilorv</a> (<b><a href="/wiki/User_talk:Bilorv" title="User talk:Bilorv"><span style="color:purple">talk</span></a></b>) <a href="https://en.wikipedia.org/wiki/Talk:BPP_(complexity)#c-Bilorv-20230128134100-62.166.189.223-20230125103300" class="ext-discussiontools-init-timestamplink">13:41, 28 January 2023 (UTC)</a><span class="ext-discussiontools-init-replylink-buttons" data-mw-thread-id="c-Bilorv-20230128134100-62.166.189.223-20230125103300"><span id="ooui-php-22" class="ext-discussiontools-init-replybutton oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-frameless oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-buttonWidget" data-ooui='{"_":"OO.ui.ButtonWidget","rel":["nofollow"],"framed":false,"icon":"share","label":"Reply","flags":["progressive"],"classes":["ext-discussiontools-init-replybutton"]}'><a role="button" tabindex="0" rel="nofollow" class="oo-ui-buttonElement-button"><span class="oo-ui-iconElement-icon oo-ui-icon-share oo-ui-image-progressive"></span><span class="oo-ui-labelElement-label">Reply</span><span class="oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-progressive"></span></a></span></span><span data-mw-comment-end="c-Bilorv-20230128134100-62.166.189.223-20230125103300"></span></dd></dl>    </section></div> <noscript><img src="https://login.m.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&mobile=1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript><div class="ext-discussiontools-init-new-topic"><span data-event-name='talkpage.add-topic' id='ooui-php-30' class='ext-discussiontools-init-new-topic-button oo-ui-widget oo-ui-widget-enabled oo-ui-buttonElement oo-ui-buttonElement-framed oo-ui-iconElement oo-ui-labelElement oo-ui-flaggedElement-progressive oo-ui-flaggedElement-primary oo-ui-buttonWidget' data-ooui='{"_":"OO.ui.ButtonWidget","href":"\/w\/index.php?title=Talk:BPP_(complexity)&action=edit&section=new","rel":["nofollow"],"icon":"speechBubbleAdd","label":"Add topic","flags":["progressive","primary"],"classes":["ext-discussiontools-init-new-topic-button"]}'><a role='button' tabindex='0' href='/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=new' rel='nofollow' class='oo-ui-buttonElement-button'><span class='oo-ui-iconElement-icon oo-ui-icon-speechBubbleAdd oo-ui-image-invert'></span><span class='oo-ui-labelElement-label'>Add topic</span><span class='oo-ui-indicatorElement-indicator oo-ui-indicatorElement-noIndicator oo-ui-image-invert'></span></a></span></div> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Talk:BPP_(complexity)&oldid=1200310634">https://en.wikipedia.org/w/index.php?title=Talk:BPP_(complexity)&oldid=1200310634</a>"</div></div> </div> <div class="post-content" id="page-secondary-actions"> </div> </main> <footer class="mw-footer minerva-footer" role="contentinfo"> <a class="last-modified-bar" href="/w/index.php?title=Talk:BPP_(complexity)&action=history"> <div class="post-content last-modified-bar__content"> <span class="minerva-icon minerva-icon-size-medium minerva-icon--modified-history"></span> <span class="last-modified-bar__text modified-enhancement" data-user-name="Cewbot" data-user-gender="unknown" data-timestamp="1706511152"> <span>Last edited on 29 January 2024, at 06:52</span> </span> <span class="minerva-icon minerva-icon-size-small minerva-icon--expand"></span> </div> </a> <div class="post-content footer-content"> <div id="p-lang"> <h4>Languages</h4> <section> <ul id="p-variants" class="minerva-languages"></ul> <ul class="minerva-languages"></ul> <p>This page is not available in other languages.</p> </section> </div> <div class="minerva-footer-logo"><img src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" alt="Wikipedia" width="120" height="18" style="width: 7.5em; height: 1.125em;"/> </div> <ul id="footer-info" class="footer-info hlist hlist-separated"> <li id="footer-info-lastmod"> This page was last edited on 29 January 2024, at 06:52<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Content is available under <a class="external" rel="nofollow" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">CC BY-SA 4.0</a> unless otherwise noted.</li> </ul> <ul id="footer-places" class="footer-places hlist hlist-separated"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-terms-use"><a href="https://foundation.m.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use">Terms of Use</a></li> <li id="footer-places-desktop-toggle"><a id="mw-mf-display-toggle" href="//en.wikipedia.org/w/index.php?title=Talk:BPP_(complexity)&mobileaction=toggle_view_desktop" data-event-name="switch_to_desktop">Desktop</a></li> </ul> </div> </footer> </div> </div> <div class="mw-notification-area" data-mw="interface"></div>  <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-jhvjh","wgBackendResponseTime":161,"wgDiscussionToolsPageThreads":[{"headingLevel":2,"name":"h-Deco-2005-12-03T19:29:00.000Z","type":"heading","level":0,"id":"h-Untitled-2005-12-03T19:29:00.000Z","replies":[{"timestamp":"2005-12-03T19:29:00.000Z","author":"Deco","type":"comment","level":1,"id":"c-Deco-2005-12-03T19:29:00.000Z-Untitled","replies":[]}]},{"headingLevel":2,"name":"h-Deco-2005-12-03T19:37:00.000Z","type":"heading","level":0,"id":"h-P=NP_or_P=BPP?-2005-12-03T19:37:00.000Z","replies":[{"timestamp":"2005-12-03T19:37:00.000Z","author":"Deco","type":"comment","level":1,"id":"c-Deco-2005-12-03T19:37:00.000Z-P=NP_or_P=BPP?","replies":[{"timestamp":"2005-12-04T18:18:00.000Z","author":"MarkSweep","type":"comment","level":2,"id":"c-MarkSweep-2005-12-04T18:18:00.000Z-Deco-2005-12-03T19:37:00.000Z","replies":[]}]}]},{"headingLevel":2,"name":"h-MarkSweep-2005-12-04T18:36:00.000Z","type":"heading","level":0,"id":"h-BPP_and_P_terminology/linguistics-2005-12-04T18:36:00.000Z","replies":[{"timestamp":"2005-12-04T18:36:00.000Z","author":"MarkSweep","type":"comment","level":1,"id":"c-MarkSweep-2005-12-04T18:36:00.000Z-BPP_and_P_terminology/linguistics","replies":[{"timestamp":"2005-12-04T19:25:00.000Z","author":"Deco","type":"comment","level":2,"id":"c-Deco-2005-12-04T19:25:00.000Z-MarkSweep-2005-12-04T18:36:00.000Z","replies":[{"timestamp":"2006-03-24T00:43:00.000Z","author":"Ben Standeven","type":"comment","level":3,"id":"c-Ben_Standeven-2006-03-24T00:43:00.000Z-Deco-2005-12-04T19:25:00.000Z","replies":[{"timestamp":"2010-07-13T20:15:00.000Z","author":"JumpDiscont","type":"comment","level":4,"id":"c-JumpDiscont-2010-07-13T20:15:00.000Z-Ben_Standeven-2006-03-24T00:43:00.000Z","replies":[{"timestamp":"2010-07-14T11:42:00.000Z","author":"EmilJ","type":"comment","level":5,"id":"c-EmilJ-2010-07-14T11:42:00.000Z-JumpDiscont-2010-07-13T20:15:00.000Z","replies":[{"timestamp":"2010-07-14T20:20:00.000Z","author":"JumpDiscont","type":"comment","level":6,"id":"c-JumpDiscont-2010-07-14T20:20:00.000Z-EmilJ-2010-07-14T11:42:00.000Z","replies":[{"timestamp":"2010-07-15T10:08:00.000Z","author":"EmilJ","type":"comment","level":7,"id":"c-EmilJ-2010-07-15T10:08:00.000Z-JumpDiscont-2010-07-14T20:20:00.000Z","replies":[],"displayName":"Emil"}]}],"displayName":"Emil"}]}]}]}]}]},{"headingLevel":2,"name":"h-Ozga-2006-03-27T20:18:00.000Z","type":"heading","level":0,"id":"h-BPP_and_Monte_Carlo-2006-03-27T20:18:00.000Z","replies":[{"timestamp":"2006-03-27T20:18:00.000Z","author":"Ozga","type":"comment","level":1,"id":"c-Ozga-2006-03-27T20:18:00.000Z-BPP_and_Monte_Carlo","replies":[{"timestamp":"2006-03-27T22:39:00.000Z","author":"EJ","type":"comment","level":2,"id":"c-EJ-2006-03-27T22:39:00.000Z-Ozga-2006-03-27T20:18:00.000Z","replies":[]}]},{"timestamp":"2006-03-28T05:36:00.000Z","author":"Ozga","type":"comment","level":1,"id":"c-Ozga-2006-03-28T05:36:00.000Z-BPP_and_Monte_Carlo","replies":[]},{"timestamp":"2006-03-30T17:06:00.000Z","author":"Ozga","type":"comment","level":1,"id":"c-Ozga-2006-03-30T17:06:00.000Z-BPP_and_Monte_Carlo","replies":[]},{"timestamp":"2007-08-17T04:44:00.000Z","author":"Sadeq","type":"comment","level":1,"id":"c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo","replies":[]}]},{"headingLevel":2,"name":"h-EmilJ-2009-11-11T19:07:00.000Z","type":"heading","level":0,"id":"h-Bounds-2009-11-11T19:07:00.000Z","replies":[{"timestamp":"2009-11-11T19:07:00.000Z","author":"EmilJ","type":"comment","level":1,"id":"c-EmilJ-2009-11-11T19:07:00.000Z-Bounds","replies":[{"timestamp":"2009-11-11T22:00:00.000Z","author":"RobinK","type":"comment","level":2,"id":"c-RobinK-2009-11-11T22:00:00.000Z-EmilJ-2009-11-11T19:07:00.000Z","replies":[{"timestamp":"2009-11-12T11:44:00.000Z","author":"EmilJ","type":"comment","level":3,"id":"c-EmilJ-2009-11-12T11:44:00.000Z-RobinK-2009-11-11T22:00:00.000Z","replies":[{"timestamp":"2009-11-12T13:01:00.000Z","author":"RobinK","type":"comment","level":4,"id":"c-RobinK-2009-11-12T13:01:00.000Z-EmilJ-2009-11-12T11:44:00.000Z","replies":[{"timestamp":"2009-11-12T13:20:00.000Z","author":"EmilJ","type":"comment","level":5,"id":"c-EmilJ-2009-11-12T13:20:00.000Z-RobinK-2009-11-12T13:01:00.000Z","replies":[],"displayName":"Emil"}],"displayName":"Robin"}],"displayName":"Emil"}],"displayName":"Robin"}],"displayName":"Emil"}]},{"headingLevel":2,"name":"h-62.166.189.223-20230125103300","type":"heading","level":0,"id":"h-k_runs-20230125103300","replies":[{"timestamp":"20230125103300","author":"62.166.189.223","type":"comment","level":1,"id":"c-62.166.189.223-20230125103300-k_runs","replies":[{"timestamp":"20230128134100","author":"Bilorv","type":"comment","level":2,"id":"c-Bilorv-20230128134100-62.166.189.223-20230125103300","replies":[]}]}]}],"wgPageParseReport":{"discussiontools":{"limitreport-timeusage":"0.024"},"limitreport":{"cputime":"0.207","walltime":"0.320","ppvisitednodes":{"value":523,"limit":1000000},"postexpandincludesize":{"value":35276,"limit":2097152},"templateargumentsize":{"value":4027,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":6,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":15986,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 182.633 1 Template:WikiProject_banner_shell","100.00% 182.633 1 -total"," 46.15% 84.280 1 Template:WikiProject_Mathematics"," 14.84% 27.111 1 Template:WikiProject_Computer_science"," 5.42% 9.906 1 Template:Tasks"," 2.54% 4.647 1 Template:Tl"," 0.87% 1.597 1 Template:Yesno"," 0.80% 1.470 2 Template:Nowrap"]},"scribunto":{"limitreport-timeusage":{"value":"0.123","limit":"10.000"},"limitreport-memusage":{"value":2010369,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-hxmhw","timestamp":"20241124185305","ttl":864000,"transientcontent":true}}});});</script> <script>(window.NORLQ=window.NORLQ||[]).push(function(){var ns,i,p,img;ns=document.getElementsByTagName('noscript');for(i=0;i<ns.length;i++){p=ns[i].nextSibling;if(p&&p.className&&p.className.indexOf('lazy-image-placeholder')>-1){img=document.createElement('img');img.setAttribute('src',p.getAttribute('data-src'));img.setAttribute('width',p.getAttribute('data-width'));img.setAttribute('height',p.getAttribute('data-height'));img.setAttribute('alt',p.getAttribute('data-alt'));p.parentNode.replaceChild(img,p);}}});</script> </body> </html>