Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(271 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
In [[computational complexity theory]], the [[complexity class]] '''2-EXPTIME''' (sometimes called '''2-EXP''') is the [[Set (mathematics)|set]] of all [[decision problem]]s solvable by a [[deterministic Turing machine]] in [[big O notation|O]](2<sup>2<sup>''p''(''n'')</sup></sup>) time, where ''p''(''n'') is a polynomial function of ''n''.
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


In terms of [[DTIME]],
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


:<math> \mbox{2-EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ 2^{n^k} } \right) . </math>
Registered users will be able to choose between the following three rendering modes:  


We know
'''MathML'''
:<math forcemathmode="mathml">E=mc^2</math>


:[[P (complexity)|P]] <math>\subseteq</math> [[NP (complexity)|NP]] <math>\subseteq</math> [[PSPACE]] <math>\subseteq</math> [[EXPTIME]] <math>\subseteq</math> [[NEXPTIME]] <math>\subseteq</math> [[EXPSPACE]] <math>\subseteq</math> '''2-EXPTIME''' <math>\subseteq</math> [[ELEMENTARY]].
<!--'''PNG''' (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an [[alternating Turing machine]] in exponential space. This is one way to see that EXPSPACE <math>\subseteq</math> 2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.<ref>Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.</ref>
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply exponential time bound <math>2^{2^{2^{n^k}}}</math>. This can be generalized to higher and higher time bounds.
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


==2-EXPTIME-complete problems==
==Demos==


Generalizations of many fully observable games are EXPTIME-complete. These games can be viewed as particular instance of a class of transition systems defined in terms of a set of state variables and actions/events that change the values of the state variables, together with the question of whether a winning strategy exists.
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:


A generalization of this class of fully observable problems to partially observable problems lifts the complexity from [[EXPTIME]]-complete to 2-EXPTIME-complete.<ref>{{ cite journal | author = Jussi Rintanen | title = Complexity of Planning with Partial Observability | journal = Proceedings of International Conference on Automated Planning and Scheduling | publisher = AAAI Press | pages = 345–354 | year = 2004 | url=http://www.informatik.uni-freiburg.de/~ki/papers/Rintanen03compl.pdf}}</ref>


==See also==
* accessibility:
* [[Double exponential function]]
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


==References==
==Test pages ==
<references/>


{{ComplexityClasses}}
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


[[Category:Complexity classes]]
*[[Inputtypes|Inputtypes (private Wikis only)]]
*[[Url2Image|Url2Image (private Wikis only)]]
==Bug reporting==
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .

Latest revision as of 22:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML

E=mc2


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"