https://complexity.subwiki.org/w/api.php?action=feedcontributions&feedformat=atom&user=VipulComplexity - User contributions [en]2026-05-14T17:09:13ZUser contributionsMediaWiki 1.41.2https://complexity.subwiki.org/w/index.php?title=MediaWiki:Sitenotice&diff=91MediaWiki:Sitenotice2024-09-15T23:04:43Z<p>Vipul: </p>
<hr />
<div>Want site search autocompletion? See [[Project:Enabling site search autocompletion|here]]<br/><br />
Encountering 429 Too Many Requests errors when browsing the site? See [[Project:429 Too Many Requests error|here]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=User:Vipul/Sandbox&diff=90User:Vipul/Sandbox2024-09-15T23:04:05Z<p>Vipul: </p>
<hr />
<div>* <math>\sqrt{7 + 2}!! + 3 = 723</math><br />
* <math>\sqrt{7 + \sqrt{4}}!! + 4! = 744</math><br />
* <math>9^{\sqrt{7 + 2}} = 729</math><br />
* <math>(7 + 2)^{\sqrt{9}} = 729</math><br />
* <math>5^{1 + 2} = 125</math><br />
* <math>6^{2 + 1} = 216</math></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=MediaWiki:Sitenotice&diff=89MediaWiki:Sitenotice2024-09-08T18:09:49Z<p>Vipul: </p>
<hr />
<div>'''This site is in the process of being migrated to a new server. Edits made until this notice has been removed may be lost.'''<br/><br />
Want site search autocompletion? See [[Project:Enabling site search autocompletion|here]]<br/><br />
Encountering 429 Too Many Requests errors when browsing the site? See [[Project:429 Too Many Requests error|here]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=MediaWiki:Sitenotice&diff=88MediaWiki:Sitenotice2024-08-18T19:53:37Z<p>Vipul: </p>
<hr />
<div>Want site search autocompletion? See [[Project:Enabling site search autocompletion|here]]<br/><br />
Encountering 429 Too Many Requests errors when browsing the site? See [[Project:429 Too Many Requests error|here]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Complexity:429_Too_Many_Requests_error&diff=87Complexity:429 Too Many Requests error2024-08-18T19:52:39Z<p>Vipul: Created page with "This content is copied from Ref:Ref:429 Too Many Requests error. If you get a 429 Too Many Requests error when browsing this site, read on. You're probably seeing this error because a large number of requests have been made from your IP address over a short period of time. That's probably a lot of requests from you or others who share your IP address (such as your home wi-fi network). Waiting a minute and then retrying should generally work. If you are an actual h..."</p>
<hr />
<div>This content is copied from [[Ref:Ref:429 Too Many Requests error]].<br />
<br />
If you get a 429 Too Many Requests error when browsing this site, read on.<br />
<br />
You're probably seeing this error because a large number of requests have been made from your IP address over a short period of time. That's probably a lot of requests from you or others who share your IP address (such as your home wi-fi network). Waiting a minute and then retrying should generally work.<br />
<br />
If you are an actual human being with a legitimate reason to be browsing the site heavily, first, thank you and sorry about this! We set rate limits to prevent bots, spiders, spammers, and malicious actors from consuming too much of our server's resources so that our server's resources can be devoted to real humans like you. Consider writing to vipulnaik1@gmail.com with your IP address to have the IP address whitelisted. You can get your IP address by [https://www.google.com/search?q=my+ip+address Googling "my IP address"] (scroll down a little bit to where Google includes the IP address in a box). NOTE: If you have both an IPv4 address and an IPv6 address, you should send both; the server supports both IPv4 and IPv6, so either may end up getting used. To check if you have an IPv6 address, try visiting [https://ipv6.google.com/ ipv6.google.com].<br />
<br />
If your IP address changes, or you are away from your home network, then you'll get rate-limited again. So if you find yourself getting rate-limited after already having been whitelisted, check if you are on a different IP address than the one for which you requested whitelisting.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=File:Site_search_autocompletion_working.png&diff=86File:Site search autocompletion working.png2024-08-18T19:51:10Z<p>Vipul: </p>
<hr />
<div></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=File:Site_search_autocompletion_broken.png&diff=85File:Site search autocompletion broken.png2024-08-18T19:50:44Z<p>Vipul: </p>
<hr />
<div></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Complexity:Enabling_site_search_autocompletion&diff=84Complexity:Enabling site search autocompletion2024-08-18T19:46:32Z<p>Vipul: Created page with "Content copied from Ref:Ref:Enabling site search autocompletion. Images used are specific to this site (Complexity). Site search autocompletion is currently broken by default on this site. This page includes details on how to get it to work, and what's going on. ==What's wrong with site search autocompletion and how to fix it== ===What's wrong=== When you start typing something in the site search bar, you'll see it stuck at "Loading search suggestions" as shown i..."</p>
<hr />
<div>Content copied from [[Ref:Ref:Enabling site search autocompletion]]. Images used are specific to this site (Complexity).<br />
<br />
Site search autocompletion is currently broken by default on this site. This page includes details on how to get it to work, and what's going on.<br />
<br />
==What's wrong with site search autocompletion and how to fix it==<br />
<br />
===What's wrong===<br />
<br />
When you start typing something in the site search bar, you'll see it stuck at "Loading search suggestions" as shown in the screenshot below:<br />
<br />
[[File:Site search autocompletion broken.png]]<br />
<br />
Note that the actual search is still working -- you just have to hit Enter after typing the search query and it'll go to the search results page. It's the autocompletion before you hit Enter that is broken.<br />
<br />
===How to fix it===<br />
<br />
To fix it, you need to follow these steps:<br />
<br />
* Write to vipulnaik1@gmail.com asking for a login to the site. Please include the following with your request: preferred username, preferred initial password (you can change it after logging in), real name (if you want it entered), email address to use (if you want an actual email address by which you can be contacted), and whether you want edit access as well. You don't need edit access for enabling site search autocompletion.<br />
* Log in to the site. Then go to [[Special:Preferences]]. Go to the Appearance section and switch the Skin from "Vector (2022)" to "Vector legacy (2010)".<br />
* Make sure to hit "Save" at the bottom.<br />
* Now you can reload the page or load a new page.<br />
<br />
Site search autocompletion should now work. Here's an example:<br />
<br />
[[File:Site search autocompletion working.png]]<br />
<br />
==More background==<br />
<br />
We've recently upgraded the MediaWiki version of this wiki from 1.35.13 to 1.41.2 (see [[Special:Version]]). The upgrade allows us to migrate the wiki to a more modern operating system version running PHP 8. With the current setup for MediaWiki 1.41.2, we're in this situation:<br />
<br />
* The "Vector legacy (2010)" skin has site search autocompletion working, but it doesn't render well on small screens. Specifically, even on small mobile screens, it still shows the left menu, and doesn't properly use the MobileFrontend extension settings.<br />
* The "Vector (2022)" skin doesn't have site search autocompletion working (see screenshots in preceding section) but it does render fine on mobile devices.<br />
<br />
It is possible to set only one default skin (that is applicable to all non-logged-in users and is the default for logged-in users who have not configured a skin for themselves). So, the selection of default skin comes down to whether it's more important for casual users to have the mobile experience working or to have site search autocompletion working. Based on a general understanding of user behavior, we believe that having a usable mobile experience is more important for casual users than having site search autocompletion.<br />
<br />
However, for power users who are using the site extensively, site search autocompletion may be important. That's why we've written this page giving guidance on how to set up site search autocompletion.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=MediaWiki:Sitenotice&diff=83MediaWiki:Sitenotice2024-08-18T19:42:02Z<p>Vipul: Blanked the page</p>
<hr />
<div></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=User:Vipul/Sandbox&diff=82User:Vipul/Sandbox2024-08-18T19:40:04Z<p>Vipul: </p>
<hr />
<div>* <math>\sqrt{7 + 2}!! + 3 = 723</math><br />
* <math>\sqrt{7 + \sqrt{4}}!! + 4! = 744</math><br />
* <math>9^{\sqrt{7 + 2}} = 729</math><br />
* <math>(7 + 2)^{\sqrt{9}} = 729</math><br />
* <math>5^{1 + 2} = 125</math></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=User:Vipul/Sandbox&diff=81User:Vipul/Sandbox2024-08-18T19:35:48Z<p>Vipul: </p>
<hr />
<div>* <math>\sqrt{7 + 2}!! + 3 = 723</math><br />
* <math>\sqrt{7 + \sqrt{4}}!! + 4! = 744</math><br />
* <math>9^{\sqrt{7 + 2}} = 729</math><br />
* <math>(7 + 2)^{\sqrt{9}} = 729</math></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=User:Vipul/Sandbox&diff=78User:Vipul/Sandbox2024-08-18T19:31:09Z<p>Vipul: </p>
<hr />
<div>* <math>\sqrt{7 + 2}!! + 3 = 723</math><br />
* <math>\sqrt{7 + \sqrt{4}}!! + 4! = 744</math><br />
* <math>9^{\sqrt{7 + 2}} = 729</math></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=MediaWiki:Sitenotice&diff=77MediaWiki:Sitenotice2024-08-18T19:22:49Z<p>Vipul: </p>
<hr />
<div>'''This wiki is in the process of being upgraded. The site may go down intermittently. Please try to avoid editing until this notice has been removed.'''</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=User:Vipul/Sandbox&diff=76User:Vipul/Sandbox2024-07-14T22:54:11Z<p>Vipul: </p>
<hr />
<div>* <math>\sqrt{7 + 2}!! + 3 = 723</math><br />
* <math>\sqrt{7 + \sqrt{4}}!! + 4! = 744</math></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=User:Vipul/Sandbox&diff=75User:Vipul/Sandbox2024-07-14T22:50:13Z<p>Vipul: Created page with "* <math>\sqrt{7 + 2}!! + 3 = 723</math>"</p>
<hr />
<div>* <math>\sqrt{7 + 2}!! + 3 = 723</math></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Cobham-Edmonds_thesis&diff=63Cobham-Edmonds thesis2011-12-28T02:48:51Z<p>Vipul: Redirected page to Cobham's thesis</p>
<hr />
<div>#redirect [[Cobham's thesis]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Church-Turing_conjecture&diff=62Church-Turing conjecture2011-12-28T02:47:29Z<p>Vipul: Redirected page to Church-Turing thesis</p>
<hr />
<div>#redirect [[Church-Turing thesis]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Church%27s_conjecture&diff=61Church's conjecture2011-12-28T02:46:35Z<p>Vipul: Redirected page to Church-Turing thesis</p>
<hr />
<div>#redirect [[Church-Turing thesis]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Turing%27s_conjecture&diff=60Turing's conjecture2011-12-28T02:46:05Z<p>Vipul: Redirected page to Church-Turing thesis</p>
<hr />
<div>#redirect [[Church-Turing thesis]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Turing%27s_thesis&diff=59Turing's thesis2011-12-28T02:45:40Z<p>Vipul: Redirected page to Church-Turing thesis</p>
<hr />
<div>#redirect [[Church-Turing thesis]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Church%27s_thesis&diff=58Church's thesis2011-12-28T02:45:05Z<p>Vipul: Redirected page to Church-Turing thesis</p>
<hr />
<div>#redirect [[Church-Turing thesis]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Church-Turing_thesis&diff=57Church-Turing thesis2011-12-28T02:44:33Z<p>Vipul: Created page with "{{intuition-to-formalism bridge thesis}} ==Statement== The '''Church-Turing thesis''' states that if a computation can be effectively carried out by some machine, then it can b..."</p>
<hr />
<div>{{intuition-to-formalism bridge thesis}}<br />
<br />
==Statement==<br />
<br />
The '''Church-Turing thesis''' states that if a computation can be effectively carried out by some machine, then it can be carried out by any of these equivalent machines or formalisms:<br />
<br />
# [[Turing machine]]s<br />
# [[lambda-calculus]]<br />
# recursive definition<br />
<br />
Note that (1)-(3) are known to be equivalent in terms of the power of things they can express and compute. What the Church-Turing thesis states is that ''any'' thing that can be effectively calculated is equivalent to all of these.<br />
<br />
The Church-Turing thesis is a thesis that bridges between an intuitive notion of effective computability and a formal model of computation. It cannot be proved in this form, because the intuitive notion of effective computability has no prior formal definition. However, if a reasonable notion of effective computability is postulated that cannot be carried out by a Turing machine, then that would disprove the Church-Turing thesis.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Nondeterministic_time_hierarchy_theorem&diff=56Nondeterministic time hierarchy theorem2011-12-28T02:38:48Z<p>Vipul: Created page with "==Statement== If <math>f</math> and <math>g</math> are time-constructible functions and <math>f(n + 1) = o(g(n))</math>, then <math>\operatorname{NTIME}(f(n))</math> is stri..."</p>
<hr />
<div>==Statement==<br />
<br />
If <math>f</math> and <math>g</math> are [[time-constructible function]]s and <math>f(n + 1) = o(g(n))</math>, then <math>\operatorname{NTIME}(f(n))</math> is strictly contained in <math>\operatorname{NTIME}(g(n))</math>.<br />
<br />
==Related facts==<br />
<br />
* [[Deterministic time hierarchy theorem]]<br />
* [[Nondeterministic space hierarchy theorem]]<br />
* [[Deterministic space hierarchy theorem]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Deterministic_time_hierarchy_theorem&diff=55Deterministic time hierarchy theorem2011-12-28T02:35:05Z<p>Vipul: Created page with "==Statement== ===Existential version=== Suppose <math>f</math> is a time-constructible function. Then, there exists a deterministic time complexity class that is strict..."</p>
<hr />
<div>==Statement==<br />
<br />
===Existential version===<br />
<br />
Suppose <math>f</math> is a [[time-constructible function]]. Then, there exists a [[deterministic time complexity class]] that is strictly larger than <math>DTIME(f(n))</math>. The explicit description of this depends on the choice of model of computation that we are using to define <math>DTIME</math>.<br />
<br />
===Explicit version===<br />
<br />
With a suitable model of computation, we can show that <math>DTIME(f(n))</math> is strictly contained in <math>DTIME(f(n) \log f(n))</math>. <br />
<br />
==Proof==<br />
<br />
The key idea behind the proof is the [[diagonalization argument]].</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Time-constructible_function&diff=54Time-constructible function2011-12-28T02:18:37Z<p>Vipul: Created page with "==Definition== A '''time-constructible function''' is a function <math>f</math> from the set of natural numbers to itself such that there exists a Turing machine that takes ..."</p>
<hr />
<div>==Definition==<br />
<br />
A '''time-constructible function''' is a function <math>f</math> from the set of natural numbers to itself such that there exists a [[Turing machine]] that takes as input <math>n</math> and outputs <math>f(n)</math> in time <math>O(f(n))</math>.<br />
<br />
Any function that bounds from above the time taken by a Turing machine must be a time-constructible function.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Fillin&diff=53Template:Fillin2011-12-28T02:15:43Z<p>Vipul: Created page with "''Fill this in later''"</p>
<hr />
<div>''Fill this in later''</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=DTIME&diff=52DTIME2011-12-28T02:15:17Z<p>Vipul: Redirected page to Deterministic time complexity class</p>
<hr />
<div>#redirect [[deterministic time complexity class]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Diagonalization_argument&diff=51Diagonalization argument2011-12-28T02:14:42Z<p>Vipul: </p>
<hr />
<div>==Definition==<br />
<br />
A '''diagonalization argument''' is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or cannot be decided by machines of a certain type.<br />
<br />
These arguments are adaptations of the [[Canton diagonalization argument]] that shows that a set (whether finite or infinite) cannot be put in bijection with its power set.<br />
<br />
The rough idea behind the relevance of the diagonalization argument is as follows: The number of available Turing machines is ''small'' because any Turing machine can itself be described by a string that is input to a universal Turing machine. On the other hand, the number of languages is ''large'' because it involves choosing arbitrary subsets of the set of all permissible strings. Thus, we can mimic the diagonalization argument and try to derive a contradiction from the assumption that all languages can be decided by machines.<br />
<br />
==Examples==<br />
<br />
* The existence of [[undecidable language]]s, i.e., it is possible for there to be a language such that membership of the language cannot be decided by any Turing machine.<br />
* The unsolvability of the [[halting problem]], i.e., it is not possible to construct a Turing machine that can take as input a string and the code for a Turing machine and determine whether the Turing machine will halt on that string.<br />
* [[Deterministic time hierarchy theorem]]<br />
* [[Nondeterministic time hierarchy theorem]]<br />
* [[Deterministic space hierarchy theorem]]<br />
* [[Nondeterministic space hierarchy theorem]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Diagonalization_argument&diff=50Diagonalization argument2011-12-28T02:03:40Z<p>Vipul: </p>
<hr />
<div>==Definition==<br />
<br />
A '''diagonalization argument''' is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or cannot be decided by machines of a certain type. The classic application is to showing the existence of [[undecidable language]]s via the [[halting problem]].<br />
<br />
These arguments are adaptations of the [[Canton diagonalization argument]] that shows that a set (whether finite or infinite) cannot be put in bijection with its power set.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Diagonalization_argument&diff=49Diagonalization argument2011-12-28T02:02:54Z<p>Vipul: Created page with "==Definition== A '''diagonalization argument''' is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or ..."</p>
<hr />
<div>==Definition==<br />
<br />
A '''diagonalization argument''' is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or cannot be decided by machines of a certain type. The classic application is to showing the existence of [[undecidable language]]s via the [[halting problem]].</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Deterministic_time_complexity_class&diff=48Deterministic time complexity class2011-12-28T01:57:58Z<p>Vipul: Created page with "==Definition== ===Given a model of computation for a single function=== We consider here a model of computation where deterministic Turing machines with certain constraints are..."</p>
<hr />
<div>==Definition==<br />
<br />
===Given a model of computation for a single function===<br />
<br />
We consider here a model of computation where deterministic Turing machines with certain constraints are allowed, and strings all over a fixed alphabet. The goal of the Turing machine is to determine whether the string is in a particular language or not.<br />
<br />
Suppose <math>f</math> is an (Eventually) increasing function from positive integers to positive integers. The deterministic time complexity class <math>DTIME(f(n))</math> is defined as the collection of all languages for which, for sufficiently large <math>n</math>, there exists a deterministic Turing machine that can, in at most <math>f(n)</math> steps, determine whether the string is in the language or not, where <math>n</math> is the length of the string.<br />
<br />
There are three key aspects to note:<br />
<br />
* The function is in terms of the length of the string, but the Turing machine itself is independent of the length of the string.<br />
* The time complexity is ''worst case'' complexity over all strings of length <math>n</math>.<br />
* We are interested in the behavior for sufficiently large <math>n</math> only.<br />
<br />
===Given a model of computation for a family of functions===<br />
<br />
{{fillin}}<br />
<br />
===General definition===<br />
<br />
In general, deterministic time complexity classes are ill defined because the smallest number of steps that can be taken by an algorithm depends heavily on the model of computation. Roughly speaking, the specifics of the model of computation can introduce a multiplicative error that is roughly polynomial in the length of the string. Thus, in practice, we consider deterministic time complexity classes for families of functions with the property that multiplying a function in the family by a polynomial with positive leading coefficient gives a function that is still bounded from above by a function in the family.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=47P2011-12-28T01:49:14Z<p>Vipul: /* Formal definitions */</p>
<hr />
<div>==Definition==<br />
<br />
===Loose definition===<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is a [[deterministic time complexity class]] defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the ''polynomial'' is an ''upper bound'' on the time taken, it is in terms of the ''length'' of the string, it is a ''worst case'' measure (i.e., worst case over all possible strings of the length), and we are interested in the ''asymptotic'' behavior for sufficiently large strings.<br />
<br />
===Formal definitions===<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a (deterministic) [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a (deterministic) [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language.<br />
<br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
===Worst case rather than average case===<br />
<br />
{{further|[[Worst case versus average case]]}}<br />
<br />
As for most complexity classes, the definition of polynomial time must take into account the ''worst case'' time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the ''average'' time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::ZPP]] (zero-error probabilistic polynomial time) || intersection of RP and co-RP || || || {{intermediate complexity classes|P|ZPP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[P is self-complementary]] || If <math>L \in P</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>P</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? || If <math>L_1 \in P</math>, and <math>L_2</math> is another language such that <math>L_1 \setminus L_2</math> and <math>L_2 \setminus L_1</math> are both finite sets of strings, then <math>L_2 \in P</math>.<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=46P2011-12-28T01:48:45Z<p>Vipul: /* Loose definition */</p>
<hr />
<div>==Definition==<br />
<br />
===Loose definition===<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is a [[deterministic time complexity class]] defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the ''polynomial'' is an ''upper bound'' on the time taken, it is in terms of the ''length'' of the string, it is a ''worst case'' measure (i.e., worst case over all possible strings of the length), and we are interested in the ''asymptotic'' behavior for sufficiently large strings.<br />
<br />
===Formal definitions===<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. <br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
===Worst case rather than average case===<br />
<br />
{{further|[[Worst case versus average case]]}}<br />
<br />
As for most complexity classes, the definition of polynomial time must take into account the ''worst case'' time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the ''average'' time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::ZPP]] (zero-error probabilistic polynomial time) || intersection of RP and co-RP || || || {{intermediate complexity classes|P|ZPP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[P is self-complementary]] || If <math>L \in P</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>P</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? || If <math>L_1 \in P</math>, and <math>L_2</math> is another language such that <math>L_1 \setminus L_2</math> and <math>L_2 \setminus L_1</math> are both finite sets of strings, then <math>L_2 \in P</math>.<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=45P2011-12-28T01:48:15Z<p>Vipul: </p>
<hr />
<div>==Definition==<br />
<br />
===Loose definition===<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is a [[time complexity class]] defined loosely as follows. A language is said to be in the polynomial time complexity class if there is a polynomial time algorithm for determining whether a string is in the language. Here, the ''polynomial'' is an ''upper bound'' on the time taken, it is in terms of the ''length'' of the string, it is a ''worst case'' measure (i.e., worst case over all possible strings of the length), and we are interested in the ''asymptotic'' behavior for sufficiently large strings.<br />
<br />
===Formal definitions===<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. <br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
===Worst case rather than average case===<br />
<br />
{{further|[[Worst case versus average case]]}}<br />
<br />
As for most complexity classes, the definition of polynomial time must take into account the ''worst case'' time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the ''average'' time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::ZPP]] (zero-error probabilistic polynomial time) || intersection of RP and co-RP || || || {{intermediate complexity classes|P|ZPP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[P is self-complementary]] || If <math>L \in P</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>P</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? || If <math>L_1 \in P</math>, and <math>L_2</math> is another language such that <math>L_1 \setminus L_2</math> and <math>L_2 \setminus L_1</math> are both finite sets of strings, then <math>L_2 \in P</math>.<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Decision_complexity_class&diff=44Template:Decision complexity class2011-12-28T01:45:17Z<p>Vipul: </p>
<hr />
<div>{{quotation|This article defines a [[decision complexity class]], i.e., a complexity class for decision problems. This means that given any language, the language is either a member of the decision complexity class or it is not a member of the decision complexity class.<nowiki>|</nowiki> [[:Category:Complexity classes|View a list of complexity classes]]}}<includeonly>[[Category:Decision complexity classes]][[Page class::Term| ]]</includeonly></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Complexity_class&diff=43Template:Complexity class2011-12-28T01:43:58Z<p>Vipul: moved Template:Complexity class to Template:Decision complexity class</p>
<hr />
<div>#REDIRECT [[Template:Decision complexity class]]</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Decision_complexity_class&diff=42Template:Decision complexity class2011-12-28T01:43:58Z<p>Vipul: moved Template:Complexity class to Template:Decision complexity class</p>
<hr />
<div>{{quotation|This article defines a [[complexity class]]. <nowiki>|</nowiki> [[:Category:Complexity classes|View a list of complexity classes]]}}<includeonly>[[Category:Complexity classes]][[Page class::Term| ]]</includeonly></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Complexity:Copyrights&diff=41Complexity:Copyrights2011-12-28T01:39:03Z<p>Vipul: Created page with "This is a common copyright notice to all subject wikis. ==General license information== All content is put up under the [http://creativecommons.org/licenses/by-sa/3.0/ Creative..."</p>
<hr />
<div>This is a common copyright notice to all subject wikis.<br />
<br />
==General license information==<br />
<br />
All content is put up under the [http://creativecommons.org/licenses/by-sa/3.0/ Creative Commons Attribute Share-Alike 3.0 license (unported)] (shorthand: CC-by-SA). Read the [http://creativehttp://ref.subwiki.org/w/skins/common/images/button_media.pngcommons.org/licenses/by-sa/3.0/legalcode full legal code here].<br />
<br />
===Exceptions===<br />
<br />
The software engine that runs the wiki is MediaWiki, and this software is licensed under the GNU General Public License, which is distinct from and currently incompatible with the Creative Commons license. Similarly, some of the extensions to the software engine are licensed by their developers using the GPL, which is incompatible with Creative Commons licenses.<br />
<br />
More information on the version of MediaWiki and extensions: [[Special:Version]].<br />
<br />
In addition, some templates may have been copied or adapted from Wikipedia or other wiki-based websites that use licenses other than Creative Commons licenses. Wikipedia uses the GNU Free Documentation License (GFDL) that, as of now, is incompatible with CC licenses. In such cases, it is clearly indicated on the page that it is licensed differently.<br />
<br />
===Short description of the license===<br />
<br />
The CC-by-SA license has the following features:<br />
<br />
# Content can be used and reused for any purposes, commercial or noncommercial.<br />
# Any public use or reuse of the material requires attribution of the original source (for attribution formats, see later in the document).<br />
# In case of adaptation or creation of derivative works, the newly created works must also be licensed under the same license (CC-by-SA) unless the creator of the derivative work takes ''explicit'' permission from the creator of the original work.<br />
<br />
===Fair use and other rights===<br />
<br />
The license cannot and does not limit fair use rights. Fair use may include quoting or copying select passages for the purposes of criticism and review.<br />
<br />
The license also cannot limit the use of data or information contained in the content on subject wikis. This means that anybody can use or reuse the facts or knowledge they gain from the subject wiki in any way they want.<br />
<br />
==Applicability of license to the subject wiki==<br />
<br />
===Examples of personal use that do not necessitate use of the license terms===<br />
<br />
* Saving, making copies, or taking printouts of pages on the subject wiki, as long as these copies are meant for personal use and are not to be distributed to others.<br />
* Learning facts from the subject wikis and using those facts as part of instruction or research.<br />
* Providing links to pages on the subject wikis.<br />
* Quoting short passages from the subject wiki in a criticism or review (it is preferable, though not legally enforceable, that a link to the original content being reviewed be provided).<br />
<br />
===Examples of personal use that necessitate use of the license terms===<br />
<br />
* Creating a mirror website by exporting pages or content in bulk: In this case, the mirror website must release the mirrored content under the same license terms and ''also'' attribute the original source with a link. Attribution formats are discussed below.<br />
* Giving handouts of pages or collections of pages to a group of people, such as students in a course: In this case, the handouts should be accompanied by an attribution that makes clear both the source and the original license terms, as well as a link to the Uniform Resource Identifier (URI) of the subject wiki.<br />
<br />
Attribution formats:<br />
<br />
* For websites: ''This content is from [{{fullurl:Main Page}} {{SITENAME}}]'' or ''This content is from [{{fullurl:Main Page}} {{fullsitetitle}}]''. Preferably, also a link to the specific pages (if any) used. The language of the attribution may be modified somewhat to indicate whether the content has been used as such, or whether changes have been made.<br />
* For print materials: ''This content is from {{SITENAME}}. The site URL is http://{{SITENAME}}.subwiki.org''<br />
<br />
Attribution of individuals who have contributed content to the subject wiki entries is ''not'' necessary. (However, this list of individuals can be tracked down, as discussed in the next section).<br />
<br />
==Uses not within the ambit of the license or fair use rights==<br />
<br />
Those who have contributed all the content to a particular subject wiki entry can republish the same content anywhere else ''without restriction'' and can also release the content elsewhere under a different license, since they own the full copyright to their content.<br />
<br />
To use the content on the wiki in a manner that is outside the terms of the license or beyond fair use rights, the individuals who have contributed that particular content need to be contacted. For any particular page, this information can be accessed using the history tab of the page. The users who have made edits to the page are the ones who need to be contacted.<br />
<br />
In case of difficulty doing this, please contact vipul.wikis@gmail.com or vipul@math.uchicago.edu for more information.<br />
<br />
==Copyright violations==<br />
<br />
All users using subject wikis are requested not to violate copyright of other authors or publishers. This includes providing links that may aid and abet copyright violation. Examples of things that may be considered copyright violation:<br />
<br />
* Putting up links to personal copies of restricted-access journal articles acquired through a personal or library subscription: This usually goes against the Terms of Service of the subscription. The exception is when the content of the articles is out of copyright.<br />
* Giving links to personal copies, or copies on filesharing systems, of books that are under copyright and where either owning or sharing a copy in that manner is against the terms of copyright.<br />
<br />
In case copyright violations are detected, please email vipul.wikis@gmail.com and vipul@math.uchicago.edu to have the matter looked into immediately.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=ZPP&diff=40ZPP2011-12-27T21:02:14Z<p>Vipul: </p>
<hr />
<div>{{complexity class}}<br />
<br />
==Definition==<br />
<br />
The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language <math>L</math> is in ZPP if there exists a [[Turing machine]] that has access to a random oracle and runs in polynomial time and has one of three outputs: ''Yes'', ''No'', and ''Undecided''. If the output is ''Yes'', the string is in <math>L</math>. If the output is ''No'', the string is not in <math>L</math>. if the output is ''Undecided'', then the string may or may not be in <math>L</math>. Further, for any fixed choice of input string, the probability of returning ''Maybe'' is bounded from above by a number strictly less than 1.<br />
<br />
This complexity class can also be defined as the intersection of the [[RP]] and [[co-RP]] complexity classes.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[contained in::RP]] (randomized polynomial time) || Unlike ZPP, there is no definitive ''No'' answer type here but only a ''Yes'' and a ''Maybe'' || || || {{intermediate complexity classes|ZPP|RP}}<br />
|-<br />
| [[contained in::co-RP]] || Unlike ZPP, there is no definitive ''Yes'' answer type here but only a ''No'' and a ''Maybe'' || || || {{intermediate complexity classes|ZPP|co-RP}}<br />
|-<br />
| [[contained in::BPP]] (bounded-error probabilistic polynomial time) || There are only ''maybe yes'' and ''maybe no'' answers, no definitive answers, but bounds on error rates || || || {{intermediate complexity classes|ZPP|BPP}}<br />
|-<br />
| [[contained in::PP]] (probabilistic polynomial time) || Like BPP, weaker bounds on error rates || || || {{intermediate complexity classes|ZPP|PP}}<br />
|-<br />
| [[contained in::NP intersect co-NP]] || || || || {{intermediate complexity classes|ZPP|NP intersect co-NP}}<br />
|-<br />
| [[contained in::NP]] || || || || <br />
|-<br />
| [[contained in::co-NP]] || || || ||<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[contains::P]] || || || ||<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=ZPP&diff=39ZPP2011-12-27T20:56:01Z<p>Vipul: Created page with "{{complexity class}} ==Definition== The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language <math>L</math>..."</p>
<hr />
<div>{{complexity class}}<br />
<br />
==Definition==<br />
<br />
The '''zero-error probabilistic polynomial time''' complexity class, abbreviated '''ZPP''', is defined as follows. A language <math>L</math> is in ZPP if there exists a [[Turing machine]] that has access to a random oracle and runs in polynomial time and has one of three outputs: ''Yes'', ''No'', and ''Undecided''. If the output is ''Yes'', the string is in <math>L</math>. If the output is ''No'', the string is not in <math>L</math>. if the output is ''Undecided'', then the string may or may not be in <math>L</math>. Further, for any fixed choice of input string, the probability of returning ''Maybe'' is bounded from above by a number strictly less than 1.<br />
<br />
This complexity class can also be defined as the intersection of the [[RP]] and [[co-RP]] complexity classes.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=38P2011-12-27T20:52:01Z<p>Vipul: /* Larger complexity classes */</p>
<hr />
<div>==Definition==<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is defined as follows. A language <math>L</math> is said to be in the polynomial time complexity class if it satisfies the following equivalent conditions:<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. <br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
===Worst case rather than average case===<br />
<br />
{{further|[[Worst case versus average case]]}}<br />
<br />
As for most complexity classes, the definition of polynomial time must take into account the ''worst case'' time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the ''average'' time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::ZPP]] (zero-error probabilistic polynomial time) || intersection of RP and co-RP || || || {{intermediate complexity classes|P|ZPP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[P is self-complementary]] || If <math>L \in P</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>P</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? || If <math>L_1 \in P</math>, and <math>L_2</math> is another language such that <math>L_1 \setminus L_2</math> and <math>L_2 \setminus L_1</math> are both finite sets of strings, then <math>L_2 \in P</math>.<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Further&diff=37Template:Further2011-12-27T20:50:36Z<p>Vipul: Created page with "<tt>Further information: {{{1}}}</tt>"</p>
<hr />
<div><tt>Further information: {{{1}}}</tt></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=36P2011-12-27T20:50:20Z<p>Vipul: /* Key features */</p>
<hr />
<div>==Definition==<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is defined as follows. A language <math>L</math> is said to be in the polynomial time complexity class if it satisfies the following equivalent conditions:<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. <br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
===Worst case rather than average case===<br />
<br />
{{further|[[Worst case versus average case]]}}<br />
<br />
As for most complexity classes, the definition of polynomial time must take into account the ''worst case'' time taken among possible input strings, including both the strings that are in the language and the strings that are not in the language. We are not trying to compute the ''average'' time taken among all possible input strings. It is true that a polynomial time algorithm must be polynomial time on average as well, but the converse need not be true.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[P is self-complementary]] || If <math>L \in P</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>P</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? || If <math>L_1 \in P</math>, and <math>L_2</math> is another language such that <math>L_1 \setminus L_2</math> and <math>L_2 \setminus L_1</math> are both finite sets of strings, then <math>L_2 \in P</math>.<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=RP&diff=35RP2011-12-27T20:47:31Z<p>Vipul: Created page with "{{complexity class}} ==Definition== '''RP''' or '''randomized polynomial time''' is a complexity class that can loosely be described as a class of languages in which membership..."</p>
<hr />
<div>{{complexity class}}<br />
<br />
==Definition==<br />
<br />
'''RP''' or '''randomized polynomial time''' is a complexity class that can loosely be described as a class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, where a ''Yes'' answer for a given string always means that the string is in the language, and, for any string in the language, the probability that a ''No/Maybe'' answer would be returned ''for that string'' is bounded from above by a number strictly less than 1.<br />
<br />
There are three aspects to this:<br />
<br />
* The algorithm has access to a random oracle, that may provide up to polynomially many pure random bits that the algorithm can use.<br />
* The probability of giving a wrong answer is measured as the probability ''over'' the choices of random bits but ''not'' over the choice of input strings. Rather, for input strings, we are still interested in the worst case probability.</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Complexity_class_containment&diff=34Template:Complexity class containment2011-12-27T20:43:03Z<p>Vipul: </p>
<hr />
<div>{{quotation|This article gives the statement, and proof, of one complexity class being contained in another one. The smaller complexity class is [[fact about::{{{smaller}}}]][[uses class membership of::{{{smaller}}}| ]] and the larger complexity class is [[fact about::{{{larger}}}]][[proves class membership of::{{{larger}}}| ]].}}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=Template:Decision_complexity_class&diff=33Template:Decision complexity class2011-12-27T20:38:50Z<p>Vipul: Created page with "{{quotation|This article defines a complexity class. <nowiki>|</nowiki> View a list of complexity classes}}<includeonly>[[Category:Complexity..."</p>
<hr />
<div>{{quotation|This article defines a [[complexity class]]. <nowiki>|</nowiki> [[:Category:Complexity classes|View a list of complexity classes]]}}<includeonly>[[Category:Complexity classes]][[Page class::Term| ]]</includeonly></div>Vipulhttps://complexity.subwiki.org/w/index.php?title=BPP&diff=32BPP2011-12-27T20:37:20Z<p>Vipul: /* Smaller complexity classes */</p>
<hr />
<div>{{complexity class}}<br />
<br />
==Definition==<br />
<br />
'''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, with the probability of error either way bounded by a number less than <math>1/2</math>.<br />
<br />
===Using <math>2/3</math> and <math>1/3</math>===<br />
<br />
More formally, a language <math>L</math> is in BPP if there exist functions <math>f</math> and <math>g</math> growing polynomially in their inputs, such that for any string of length <math>n</math>, the algorithm uses the string and a random string of length <math>f(n)</math> to output, in time at most <math>g(n)</math>, whether the string is in <math>L</math>, and the answer satisfies the following: For ''every'' choice of input string, less than <math>1/3</math> of the possible random strings of length <math>f(n)</math> give the wrong answer.<br />
<br />
Note that the probability is taken over the random string and ''not'' over the input string. For the input string, we are interested in the ''worst case'' probability, i.e., we would like a low error probability for ''all'' input strings.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::PP]] || probabilistic polynomial time; like BPP but probability of giving the correct output is allowed to equal <math>1/2</math> || [[PP contains BPP]] || ||<br />
|-<br />
| [[Contained in::P/poly]] || For any fixed input length, there is a polynomial sized advice string depending on the length, using which a polynomial time algorithm can be devised for all inputs of that length. || [[Adleman's theorem]] || Separated: [[P/poly contains undecidable languages]] || {{intermediate complexity classes|BPP|P/poly}}<br />
|-<br />
| [[Contained in::Sigma2P]] || <math>\Sigma_2</math> in the polynomial hierarchy || part of the [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || <math>\Pi_2</math> in the polynomial hierarchy || part of the [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Pi2P}}<br />
|-<br />
| [[Contained in::Sigma2P intersect Pi2P]] || <math>\Sigma_2P \cap \Pi_2P</math> || [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Sigma2P intersect Pi2P}}<br />
|-<br />
| [[Contained in::PH]] || The union of the entire polynomial hierarchy || (via Sigma2P) || open || {{intermediate complexity classes|BPP|PH}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::RP]] || randomized polynomial time -- no false positives, but possible false negatives || [[RP is in BPP]] || open||{{intermediate complexity classes|RP|BPP}}<br />
|-<br />
| [[Contains::co-RP]] || randomized polynomial time -- no false negatives, but possible false positives || [[co-RP is in BPP]] || open || {{intermediate complexity classes|co-RP|BPP}}<br />
|-<br />
| [[Contains::P]] || deterministic polynomial time || [[P is in BPP]] || open -- see [[P equals BPP conjecture]] || {{intermediate complexity classes|P|BPP}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[BPP is self-complementary]] || If <math>L \in BPP</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>BPP</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? ||<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=BPP&diff=31BPP2011-12-27T20:36:55Z<p>Vipul: /* Smaller complexity classes */</p>
<hr />
<div>{{complexity class}}<br />
<br />
==Definition==<br />
<br />
'''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, with the probability of error either way bounded by a number less than <math>1/2</math>.<br />
<br />
===Using <math>2/3</math> and <math>1/3</math>===<br />
<br />
More formally, a language <math>L</math> is in BPP if there exist functions <math>f</math> and <math>g</math> growing polynomially in their inputs, such that for any string of length <math>n</math>, the algorithm uses the string and a random string of length <math>f(n)</math> to output, in time at most <math>g(n)</math>, whether the string is in <math>L</math>, and the answer satisfies the following: For ''every'' choice of input string, less than <math>1/3</math> of the possible random strings of length <math>f(n)</math> give the wrong answer.<br />
<br />
Note that the probability is taken over the random string and ''not'' over the input string. For the input string, we are interested in the ''worst case'' probability, i.e., we would like a low error probability for ''all'' input strings.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::PP]] || probabilistic polynomial time; like BPP but probability of giving the correct output is allowed to equal <math>1/2</math> || [[PP contains BPP]] || ||<br />
|-<br />
| [[Contained in::P/poly]] || For any fixed input length, there is a polynomial sized advice string depending on the length, using which a polynomial time algorithm can be devised for all inputs of that length. || [[Adleman's theorem]] || Separated: [[P/poly contains undecidable languages]] || {{intermediate complexity classes|BPP|P/poly}}<br />
|-<br />
| [[Contained in::Sigma2P]] || <math>\Sigma_2</math> in the polynomial hierarchy || part of the [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || <math>\Pi_2</math> in the polynomial hierarchy || part of the [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Pi2P}}<br />
|-<br />
| [[Contained in::Sigma2P intersect Pi2P]] || <math>\Sigma_2P \cap \Pi_2P</math> || [[Sipser-Lautemann theorem]] || open, but if true, would imply that [[NP]] is in [[P/poly]] and hence PH collapses to BPP || {{intermediate complexity classes|BPP|Sigma2P intersect Pi2P}}<br />
|-<br />
| [[Contained in::PH]] || The union of the entire polynomial hierarchy || (via Sigma2P) || open || {{intermediate complexity classes|BPP|PH}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::RP]] || randomized polynomial time -- no false positives, but possible false negatives || [[RP is in BPP]] || open||{{intermediate complexity classes|RP|BPP}}<br />
|-<br />
| [[Contains::co-RP]] || randomized polynomial time -- no false negatives, but possible false positives || [[co-RP is in BPP]] || open || {{intermediate complexity classes|co-RP|BPP}}<br />
|-<br />
| [[Contains::P]] || deterministic polynomial time || [[P is in BPP]] || open -- see [[P equals BPP conjecture]] || {{intermediate complexity classes|P|BPP}}<br />
|}<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[BPP is self-complementary]] || If <math>L \in BPP</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>BPP</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? ||<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=30P2011-12-27T20:36:21Z<p>Vipul: /* Smaller complexity classes */</p>
<hr />
<div>==Definition==<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is defined as follows. A language <math>L</math> is said to be in the polynomial time complexity class if it satisfies the following equivalent conditions:<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. <br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}<br />
<br />
==Properties==<br />
<br />
{| class="sortable" border="1"<br />
! Property !! Satisfied? !! Proof !! Statement with symbols<br />
|-<br />
| [[satisfies property::self-complementary complexity class]] || Yes || [[P is self-complementary]] || If <math>L \in P</math>, then the complement <math>L^c</math>, defined as the set of strings ''not'' in <math>L</math>, is also in <math>P</math>.<br />
|-<br />
| determined by almost everywhere || Yes || ? || If <math>L_1 \in P</math>, and <math>L_2</math> is another language such that <math>L_1 \setminus L_2</math> and <math>L_2 \setminus L_1</math> are both finite sets of strings, then <math>L_2 \in P</math>.<br />
|}</div>Vipulhttps://complexity.subwiki.org/w/index.php?title=P&diff=29P2011-12-27T20:32:27Z<p>Vipul: /* Larger complexity classes */</p>
<hr />
<div>==Definition==<br />
<br />
The '''polynomial time''' complexity class, denoted '''PTIME''' or '''P''', is defined as follows. A language <math>L</math> is said to be in the polynomial time complexity class if it satisfies the following equivalent conditions:<br />
<br />
{| class="sortable" border="1"<br />
! No. !! Shorthand !! Definition<br />
|-<br />
| 1 || single tape Turing machine || there exists a [[Turing machine]] using a single tape for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 2 || multiple tape Turing machine || there exists a [[Turing machine]] with access to finitely many read/write tapes, including one for the input (and that allows for both reading and writing on the tape) that accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|-<br />
| 3 || machine with log-time random access || there exists a program that can perform random access on a read/write memory in time logarithmic to the amount of memory used, ''and'' the program accepts a string if and only if it is in the language and rejects it otherwise, ''and'' that always either accepts or rejects the string in a number of steps bounded by a polynomial in the length of the input string.<br />
|}<br />
<br />
Loosely speaking, a language is in P if there is a polynomial time algorithm for recognition of the language. <br />
==Key features==<br />
<br />
===Robustness based on complexity-theoretic Church-Turing thesis===<br />
<br />
The [[complexity-theoretic Church-Turing thesis]] states the notion of ''polynomial time'' is robust and does not change based on the nature of the machine, as long as we are dealing with ''deterministic'' machines, and we do not have access to random oracles or quantum computing. <br />
<br />
However, the ''degree'' of the polynomial that can be achieved does depend on the machine specifications (so some algorithms may be much faster with log-time random access than with sequential access as for the tapes in a Turing machine). There may be an algorithm on one kind of machine that takes time <math>O(N\log N)</math> but on another machine takes time <math>O(N^2)</math> where <math>N</math> is the length of the string.<br />
<br />
===Independence of algorithm from length of the string===<br />
<br />
The Turing machine, or more generally the program or algorithm used to determine whether a string is in the language, is ''independent'' of the length of the string. (Internally, it may make cases based on the length of the string, but that's a different matter). A related complexity class where the algorithm can take polynomial-sized advice based on the length of the string is termed [[P/poly]].<br />
<br />
===Asymptotic nature===<br />
<br />
The definition of the complexity class depends only on the asymptotic nature of the time taken as a function of the length of the string. In particular, if two languages have cofinite intersection (i.e., they are the same except for finitely many strings in each language that is not in the other) then one is in P if and only if the other is in P.<br />
<br />
==Relation with other complexity classes==<br />
<br />
===Larger complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contained in::RP]] (randomized polynomial time) || allows use of random bits. In polynomial time, the algorithm returns a ''Yes'' or ''Maybe'' with ''Yes'' indicating that the string is definitely in the language. Probability of saying ''Maybe'' if the string is in the language is bounded away from 1. || [[RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|RP}}<br />
|-<br />
| [[Contained in::co-RP]] || complement of a language in RP. || [[co-RP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|co-RP}}<br />
|-<br />
| [[Contained in::BPP]] (bounded-error probabilistic polynomial time)|| allows use of random bits, probability of errors both ways. || [[BPP contains P]] || open problem -- both separation and collapse plausible || {{intermediate complexity classes|P|BPP}}<br />
|-<br />
| [[Contained in::PP]] (probabilistic polynomial time) || error rates are allowed to come close to half. || [[PP contains P]] || || {{intermediate complexity classes|P|PP}}<br />
|-<br />
| [[Contained in::NP]] (nondeterministic polynomial time) || allows coming up magically with a string that helps provide "proof" || [[NP contains P]] || [[P equals NP conjecture]]. Separation is widely believed, i.e., it is believed that P is not equal to NP. || {{intermediate complexity classes|P|NP}}<br />
|-<br />
| [[Contained in::co-NP]] || complement of a language in NP. || [[co-NP contains P]] || equivalent to [[P equals NP conjecture]] || {{intermediate complexity classes|P|co-NP}}<br />
|-<br />
| [[Contained in::NP intersect co-NP]] || the language is both in NP and co-NP || [[NP intersect co-NP contains P]] || Unknown, separation plausible but unclear. || {{intermediate complexity classes|P|NP intersect co-NP}}<br />
|-<br />
| [[Contained in::Sigma2P]] || || || || {{intermediate complexity classes|P|Sigma2P}}<br />
|-<br />
| [[Contained in::Pi2P]] || || || || {{intermediate complexity classes|P|Pi2P}}<br />
|-<br />
| [[Contained in::Delta2P]] || || || || {{intermediate complexity classes|P|Delta2P}}<br />
|-<br />
| [[Contained in::PH]] (polynomial hierarchy) || || || ||{{intermediate complexity classes|P|PH}}<br />
|-<br />
| [[Contained in::PSPACE]] (polynomial space)|| algorithm that requires polynomial space to write on in addition to the read-only input. || || || {{intermediate complexity classes|P|PSPACE}}<br />
|-<br />
| [[Contained in::Quasipolynomial time]] (sometimes abbreviated QP, but that might be confused with quantum polynomial time) || time taken is exponential in a polynomial of the logarithm of the input length || || || {{intermediate complexity classes|P|Quasipolynomial time}}<br />
|-<br />
| [[Contained in::SUBEXP]] (subexponential time) || || || || {{intermediate complexity classes|P|SUBEXP}}<br />
|}<br />
<br />
===Smaller complexity classes===<br />
<br />
{| class="sortable" border="1"<br />
! Complexity class !! Meaning !! Proof of containment !! Reverse containment -- separation result or open problem !! Intermediate complexity classes<br />
|-<br />
| [[Contains::NL]] (nondeterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Can be used ''nondeterministically'' || || || || {{intermediate complexity classes|NL|P}}<br />
|-<br />
| [[Contains::L]] (deterministic logspace) || in addition to read-only input, read/write workspace of length bounded by a constant times the logarithm of the length of the input string. Must be used ''nondeterministically'' || || || || {{intermediate complexity classes|L|P}}<br />
|}</div>Vipul