User contributions for Vipul
28 December 2011
- 02:1502:15, 28 December 2011 diff hist +49 N DTIME Redirected page to Deterministic time complexity class current
- 02:1402:14, 28 December 2011 diff hist +1,029 Diagonalization argument No edit summary current
- 02:0302:03, 28 December 2011 diff hist +174 Diagonalization argument No edit summary
- 02:0202:02, 28 December 2011 diff hist +336 N Diagonalization argument 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 ..."
- 01:5701:57, 28 December 2011 diff hist +1,856 N Deterministic time complexity class 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..." current
- 01:4901:49, 28 December 2011 diff hist +32 P →Formal definitions current
- 01:4801:48, 28 December 2011 diff hist +14 P →Loose definition
- 01:4801:48, 28 December 2011 diff hist +401 P No edit summary
- 01:4501:45, 28 December 2011 diff hist +222 Template:Decision complexity class No edit summary current
- 01:4301:43, 28 December 2011 diff hist +48 N Template:Complexity class moved Template:Complexity class to Template:Decision complexity class current
- 01:4301:43, 28 December 2011 diff hist 0 m Template:Decision complexity class moved Template:Complexity class to Template:Decision complexity class
- 01:3901:39, 28 December 2011 diff hist +5,870 N Complexity:Copyrights 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..." current
27 December 2011
- 21:0221:02, 27 December 2011 diff hist +1,475 ZPP No edit summary current
- 20:5620:56, 27 December 2011 diff hist +813 N ZPP 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>..."
- 20:5220:52, 27 December 2011 diff hist +153 P →Larger complexity classes
- 20:5020:50, 27 December 2011 diff hist +37 N Template:Further Created page with "<tt>Further information: {{{1}}}</tt>" current
- 20:5020:50, 27 December 2011 diff hist +552 P →Key features
- 20:4720:47, 27 December 2011 diff hist +923 N RP 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..." current
- 20:4320:43, 27 December 2011 diff hist −4 Template:Complexity class containment No edit summary current
- 20:3820:38, 27 December 2011 diff hist +224 N Template:Decision complexity class Created page with "{{quotation|This article defines a complexity class. <nowiki>|</nowiki> View a list of complexity classes}}<includeonly>[[Category:Complexity..."
- 20:3720:37, 27 December 2011 diff hist +16 BPP →Smaller complexity classes current
- 20:3620:36, 27 December 2011 diff hist +406 BPP →Smaller complexity classes
- 20:3620:36, 27 December 2011 diff hist +622 P →Smaller complexity classes
- 20:3220:32, 27 December 2011 diff hist +984 P →Larger complexity classes
- 20:2820:28, 27 December 2011 diff hist +978 P →Larger complexity classes
- 20:2320:23, 27 December 2011 diff hist +3,059 P No edit summary
- 20:0720:07, 27 December 2011 diff hist +15 N Polynomial time moved Polynomial time to P over redirect current
- 20:0720:07, 27 December 2011 diff hist 0 m P moved Polynomial time to P over redirect
- 20:0720:07, 27 December 2011 diff hist +2,035 N P Created page with "==Definition== 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 ..."
- 19:5919:59, 27 December 2011 diff hist +18 Template:Quotation No edit summary current
13 August 2010
- 00:5200:52, 13 August 2010 diff hist +1,233 N Karp-Lipton theorem Created page with "==Statement== ===Statement in terms of complexity classes=== The theorem has the following equivalent formulations. Pick any equivalent formulation of the conditional -- the th..." current
- 00:4300:43, 13 August 2010 diff hist +914 N Sipser-Lautemann theorem Created page with "{{complexity class containment|smaller = BPP|larger = Sigma2P}} {{complexity class containment|smaller = BPP|larger = Pi2P}} {{complexity class containment|smaller = BPP|larger =..." current
- 00:3700:37, 13 August 2010 diff hist +38 N Pi2P contains BPP Redirected page to Sipser-Lautemann theorem current
- 00:3600:36, 13 August 2010 diff hist +38 N Sigma2P contains BPP Redirected page to Sipser-Lautemann theorem current
- 00:3500:35, 13 August 2010 diff hist +31 N P/poly contains BPP Redirected page to Adleman's theorem current
- 00:3500:35, 13 August 2010 diff hist +38 N BPP is in Sigma2P Redirected page to Sipser-Lautemann theorem current
- 00:3400:34, 13 August 2010 diff hist +336 N Template:Complexity class containment Created page with "{{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}}}]][[..."
- 00:3200:32, 13 August 2010 diff hist −5 Adleman's theorem →Loose philosophical formulation current
- 00:3200:32, 13 August 2010 diff hist +788 N Adleman's theorem Created page with "{{complexity class containment| smaller = BPP| larger = P/poly}} ==Statement== ===In terms of complexity classes=== The complexity class BPP (bounded error probabilistic p..."
- 00:2600:26, 13 August 2010 diff hist +31 N BPP is in P/poly Redirected page to Adleman's theorem current
- 00:2500:25, 13 August 2010 diff hist +843 BPP No edit summary
- 00:1700:17, 13 August 2010 diff hist +91 N Template:Intermediate complexity classes Created page with "{{#ask: [[contains::{{{1}}}]][[contained in::{{{2}}}]]|limit = 0|searchlabel = click here}}" current
- 00:1600:16, 13 August 2010 diff hist +2,844 N BPP Created page with "{{complexity class}} ==Definition== '''BPP''' or '''bounded-error probabilistic polynomial time''' is a complexity class that can loosely be described as the class of languages..."
12 August 2010
- 22:5922:59, 12 August 2010 diff hist −435 Main Page Replaced content with "{{top notice}}" current
- 22:5722:57, 12 August 2010 diff hist +12 N Template:Sitestatus Created page with "barely begun" current
- 22:5722:57, 12 August 2010 diff hist +48 N MediaWiki:Sitenotice Created page with "{{fullsitetitle}} ({{sitestatus}})"
- 22:5622:56, 12 August 2010 diff hist +38 N Template:Fullsitetitle Created page with "Complexity, The Complexity Theory Wiki" current
- 22:5522:55, 12 August 2010 diff hist +238 N Template:Top notice Created page with "{{quotation|Welcome to '''{{fullsitetitle}}'''. The wiki has just been set up and content will be added later. It is part of a broader subject wikis initiative -- see the [[Ref:M..." current
- 22:5422:54, 12 August 2010 diff hist +7 Template:Quotation No edit summary
- 22:5422:54, 12 August 2010 diff hist +302 N Template:Quotation Created page with "<blockquote class="toccolours" style="float:none; padding: 10px 15px 10px 15px; display:table;"> {{{1<noinclude>| {{Lorem}}</noinclude>}}}</blockquote><noinclude>''Thi..."