Proper complexity function - Revision history

Thatsme314: formatting

2022-04-06T03:16:15Z

formatting

← Previous revision		Revision as of 03:16, 6 April 2022
Line 6:		Line 6:

	Similar notions include honest functions, [[space-constructible function]]s, and [[time-constructible function]]s.		Similar notions include honest functions, [[space-constructible function]]s, and [[time-constructible function]]s.

	<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28</ref>

	==References==		==References==
	{{Reflist}}		{{Reflist}}
			{{cite book \|last1=Myashnikov \|first1=Alexei \|last2=Shpilrain \|first2=Vladimir \|last3=Ushakov \|first3=Vladimir \|title=Group-based Cryptography \|date=2008 \|publisher=Birkhauser \|isbn=978-3-7643-8826-3 \|page=28}}

	{{DEFAULTSORT:Proper Complexity Function}}		{{DEFAULTSORT:Proper Complexity Function}}

2022-04-06T02:40:05Z

grammar

← Previous revision		Revision as of 02:40, 6 April 2022
Line 3:		Line 3:
	* there exists a ''k''-string [[Turing machine]] ''M'' such that on any input of length ''n'', ''M'' halts after O(''n'' + ''f''(''n'')) steps, uses O(''f''(''n'')) space, and outputs ''f''(''n'') consecutive blanks.		* there exists a ''k''-string [[Turing machine]] ''M'' such that on any input of length ''n'', ''M'' halts after O(''n'' + ''f''(''n'')) steps, uses O(''f''(''n'')) space, and outputs ''f''(''n'') consecutive blanks.

	If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2<sup>''f''</sup>, are also proper complexity functions.		If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2<sup>''f''</sup> are also proper complexity functions.

	Similar notions include honest ~~function~~, [[space-constructible function]], and [[time-constructible function]].		Similar notions include honest functions, [[space-constructible function]]s, and [[time-constructible function]]s.

	<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28</ref>		<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28</ref>

2014-05-23T22:30:47Z

WP:CHECKWIKI error fix for #52. Do general fixes if a problem exists. - using AWB

← Previous revision		Revision as of 22:30, 23 May 2014
Line 7:		Line 7:
	Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]].		Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]].

		⚫	<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28</ref>
⚫	{{DEFAULTSORT:Proper Complexity Function}}
⚫	[[Category:Computational complexity theory]]
⚫	<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28 </ref>

	==References==		==References==
	{{Reflist}}		{{Reflist}}

		⚫	{{DEFAULTSORT:Proper Complexity Function}}
		⚫	[[Category:Computational complexity theory]]

2014-05-22T01:19:45Z

not unreferenced

← Previous revision		Revision as of 01:19, 22 May 2014
Line 1:		Line 1:
	{{Unreferenced\|date=December 2009}}

	A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:		A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:
	* ''f'' is nondecreasing;		* ''f'' is nondecreasing;

2014-05-06T13:54:06Z

← Previous revision		Revision as of 13:54, 6 May 2014
Line 1:		Line 1:
	{{Unreferenced\|date=December 2009}}		{{Unreferenced\|date=December 2009}}

⚫	==References==
⚫	{{Reflist}}
	A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:		A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:
	* ''f'' is nondecreasing;		* ''f'' is nondecreasing;
Line 13:		Line 12:
	[[Category:Computational complexity theory]]		[[Category:Computational complexity theory]]
	<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28 </ref>		<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28 </ref>

		⚫	==References==
		⚫	{{Reflist}}

2014-05-06T13:53:50Z

← Previous revision		Revision as of 13:53, 6 May 2014
Line 1:		Line 1:
	{{Unreferenced\|date=December 2009}}		{{Unreferenced\|date=December 2009}}
			==References==
			{{Reflist}}
	A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:		A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:
	* ''f'' is nondecreasing;		* ''f'' is nondecreasing;

2014-05-06T13:53:01Z

← Previous revision		Revision as of 13:53, 6 May 2014
Line 10:		Line 10:
	{{DEFAULTSORT:Proper Complexity Function}}		{{DEFAULTSORT:Proper Complexity Function}}
	[[Category:Computational complexity theory]]		[[Category:Computational complexity theory]]
			<ref>Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Group-based Cryptography. Birkhäuser Verlag, 2008, p.28 </ref>

2013-01-09T03:15:33Z

Bot: Removing Orphan Tag (Nolonger an Orphan) (Report Errors)

← Previous revision		Revision as of 03:15, 9 January 2013
Line 1:		Line 1:
	{{Unreferenced\|date=December 2009}}		{{Unreferenced\|date=December 2009}}
	{{Orphan\|date=December 2009}}

	A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:		A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:
	* ''f'' is nondecreasing;		* ''f'' is nondecreasing;

2009-12-17T13:54:33Z

remove Erik9bot category,outdated, tag and general fixes, added orphan tag

← Previous revision		Revision as of 13:54, 17 December 2009
Line 1:		Line 1:
			{{Unreferenced\|date=December 2009}}
			{{Orphan\|date=December 2009}}

	A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:		A '''proper complexity function''' is a function ''f'' mapping a [[natural number]] to a natural number such that:
	* ''f'' is nondecreasing;		* ''f'' is nondecreasing;
Line 7:		Line 10:
	Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]].		Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]].

			{{DEFAULTSORT:Proper Complexity Function}}
	[[Category:Computational complexity theory]]		[[Category:Computational complexity theory]]
	[[Category:Articles lacking sources (Erik9bot)]]

2009-10-27T23:57:24Z

Removed broken link for honest function.

← Previous revision		Revision as of 23:57, 27 October 2009
Line 5:		Line 5:
	If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2<sup>''f''</sup>, are also proper complexity functions.		If ''f'' and ''g'' are two proper complexity functions, then ''f'' + ''g'', ''fg'', and 2<sup>''f''</sup>, are also proper complexity functions.

	Similar notions include [[honest function]], [[space-constructible function]], and [[time-constructible function]].		Similar notions include honest function, [[space-constructible function]], and [[time-constructible function]].

	[[Category:Computational complexity theory]]		[[Category:Computational complexity theory]]