CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Talk:BPP (complexity) - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";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":"63a43e60-272d-4e41-9b68-b47c8c3ddd4b","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":["*"],"wgCategories":["Start-Class mathematics articles","Mid-priority mathematics articles","Start-Class Computer science articles","Mid-importance Computer science articles","WikiProject Computer science articles"],"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"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgDiscussionToolsFeaturesEnabled":{"replytool":true,"newtopictool":true,"sourcemodetoolbar":true,"topicsubscription":false,"autotopicsub":false,"visualenhancements":false,"visualenhancements_reply":false,"visualenhancements_pageframe":false},"wgDiscussionToolsFallbackEditMode":"source","wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":true, "wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};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","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","mediawiki.codex.messagebox.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready", "ext.wikimediaBadges":"ready"};RLPAGEMODULES=["site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.discussionTools.init","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","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.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cmediawiki.codex.messagebox.styles%7Cmediawiki.widgets.styles%7Coojs-ui-core.icons%2Cstyles%7Coojs-ui.styles.indicators%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles&only=styles&printable=1&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&printable=1&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&printable=1&skin=vector-2022"> <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="noindex,follow,max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Talk:BPP (complexity) - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Talk:BPP_(complexity)"> <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="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <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 skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-1 ns-talk mw-editable page-Talk_BPP_complexity rootpage-Talk_BPP_complexity skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Talk%3ABPP+%28complexity%29&returntoquery=printable%3Dyes" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Talk%3ABPP+%28complexity%29&returntoquery=printable%3Dyes" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Talk%3ABPP+%28complexity%29&returntoquery=printable%3Dyes" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Talk%3ABPP+%28complexity%29&returntoquery=printable%3Dyes" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Untitled" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Untitled"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Untitled</span> </div> </a> <span class="ext-discussiontools-init-sidebar-meta">1 comment</span> <ul id="toc-Untitled-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-P=NP_or_P=BPP?" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#P=NP_or_P=BPP?"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>P=NP or P=BPP?</span> </div> </a> <span class="ext-discussiontools-init-sidebar-meta">2 comments</span> <ul id="toc-P=NP_or_P=BPP?-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-BPP_and_P_terminology/linguistics" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#BPP_and_P_terminology/linguistics"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>BPP and P terminology/linguistics</span> </div> </a> <span class="ext-discussiontools-init-sidebar-meta">7 comments</span> <ul id="toc-BPP_and_P_terminology/linguistics-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-BPP_and_Monte_Carlo" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#BPP_and_Monte_Carlo"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>BPP and Monte Carlo</span> </div> </a> <span class="ext-discussiontools-init-sidebar-meta">5 comments</span> <ul id="toc-BPP_and_Monte_Carlo-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bounds" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bounds"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Bounds</span> </div> </a> <span class="ext-discussiontools-init-sidebar-meta">5 comments</span> <ul id="toc-Bounds-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-k_runs" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#k_runs"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>k runs</span> </div> </a> <span class="ext-discussiontools-init-sidebar-meta">2 comments</span> <ul id="toc-k_runs-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <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 id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang mw-portlet-lang-icon-only" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector-empty" aria-label="This article exist only in this language. Add the article for other languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-portlet-lang-heading-empty" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language mw-ui-icon-wikimedia-language"></span> <span class="vector-dropdown-label-text">Add languages</span> </label> <div class="vector-dropdown-content"> <div class="mw-portlet-empty-language-selector-body"> Page contents not supported in other languages. </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="vector-tab-noicon mw-list-item"><a href="/wiki/BPP_(complexity)" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Talk:BPP_(complexity)" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Talk:BPP_(complexity)"><span>Read</span></a></li><li id="ca-edit" class="istalk vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-addsection" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=new" title="Start a new section [+]" accesskey="+"><span>Add topic</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Talk:BPP_(complexity)"><span>Read</span></a></li><li id="ca-more-edit" class="istalk vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-addsection" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=edit&section=new"><span>Add topic</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Talk:BPP_(complexity)" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Talk:BPP_(complexity)" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&oldid=1200310634" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Talk:BPP_(complexity)&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fw%2Findex.php%3Ftitle%3DTalk%3ABPP_%28complexity%29%26printable%3Dyes"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fw%2Findex.php%3Ftitle%3DTalk%3ABPP_%28complexity%29%26printable%3Dyes"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Talk%3ABPP_%28complexity%29&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects emptyPortlet" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="cdx-message cdx-message--block cdx-message--warning"><span class="cdx-message__icon"></span><div class="cdx-message__content">The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.</div></div><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><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> <meta property="mw:PageProp/toc"/> <div class="mw-heading mw-heading2 ext-discussiontools-init-section"><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><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"></div><div class="ext-discussiontools-init-section-actions"></div></div></div> <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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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> <div class="mw-heading mw-heading2 ext-discussiontools-init-section"><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><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"></div><div class="ext-discussiontools-init-section-actions"></div></div></div> <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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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> <div class="mw-heading mw-heading2 ext-discussiontools-init-section"><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><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"></div><div class="ext-discussiontools-init-section-actions"></div></div></div> <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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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> <div class="mw-heading mw-heading2 ext-discussiontools-init-section"><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><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"></div><div class="ext-discussiontools-init-section-actions"></div></div></div> <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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</span></span><span data-mw-comment-end="c-Sadeq-2007-08-17T04:44:00.000Z-BPP_and_Monte_Carlo"></span> </p> <div class="mw-heading mw-heading2 ext-discussiontools-init-section"><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><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"></div><div class="ext-discussiontools-init-section-actions"></div></div></div> <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><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}}"/></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><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}\,}"/></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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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> <div class="mw-heading mw-heading2 ext-discussiontools-init-section"><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><div class="ext-discussiontools-init-section-bar"><div class="ext-discussiontools-init-section-metadata"></div><div class="ext-discussiontools-init-section-actions"></div></div></div> <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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</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><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}}"/></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><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}}"/></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 class="ext-discussiontools-init-replylink-bracket">[</span><a class="ext-discussiontools-init-replylink-reply" role="button" tabindex="0" href="">reply</a><span class="ext-discussiontools-init-replylink-bracket">]</span></span><span data-mw-comment-end="c-Bilorv-20230128134100-62.166.189.223-20230125103300"></span></dd></dl>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <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 id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Start-Class_mathematics_articles" title="Category:Start-Class mathematics articles">Start-Class mathematics articles</a></li><li><a href="/wiki/Category:Mid-priority_mathematics_articles" title="Category:Mid-priority mathematics articles">Mid-priority mathematics articles</a></li><li><a href="/wiki/Category:Start-Class_Computer_science_articles" title="Category:Start-Class Computer science articles">Start-Class Computer science articles</a></li><li><a href="/wiki/Category:Mid-importance_Computer_science_articles" title="Category:Mid-importance Computer science articles">Mid-importance Computer science articles</a></li><li><a href="/wiki/Category:WikiProject_Computer_science_articles" title="Category:WikiProject Computer science articles">WikiProject Computer science articles</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <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">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <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-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Talk:BPP_(complexity)&printable=yes&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-dtnhv","wgBackendResponseTime":103,"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.027"},"limitreport":{"cputime":"0.243","walltime":"0.370","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% 204.995 1 Template:WikiProject_banner_shell","100.00% 204.995 1 -total"," 45.99% 94.276 1 Template:WikiProject_Mathematics"," 13.79% 28.273 1 Template:WikiProject_Computer_science"," 4.80% 9.830 1 Template:Tasks"," 2.02% 4.135 1 Template:Tl"," 0.81% 1.666 1 Template:Yesno"," 0.63% 1.287 2 Template:Nowrap"]},"scribunto":{"limitreport-timeusage":{"value":"0.142","limit":"10.000"},"limitreport-memusage":{"value":2010401,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-f9ddp","timestamp":"20241124225148","ttl":864000,"transientcontent":true}}});});</script> </body> </html>