User:Argentpepper/Sandbox/Glossary - Revision history

Argentpepper: add span with id to appropriate definitions

2013-02-01T23:10:12Z

add span with id to appropriate definitions

Argentpepper: add span with id to block sensitivity and certificate complexity

2013-02-01T23:05:42Z

add span with id to block sensitivity and certificate complexity

Argentpepper: /* A */ add span with id to alphabet

2013-02-01T23:04:28Z

A: add span with id to alphabet

Argentpepper: /* Z */ HTML attribute should have quotes

2013-02-01T23:03:17Z

Z: HTML attribute should have quotes

Argentpepper: /* Z */ use built-in definition list syntax

2013-02-01T23:03:02Z

Z: use built-in definition list syntax

Argentpepper: /* W */ use built-in definition list syntax

2013-02-01T23:02:36Z

W: use built-in definition list syntax

Argentpepper: /* U */ use built-in definition list syntax

2013-02-01T23:01:43Z

U: use built-in definition list syntax

Argentpepper: /* T */ use built-in definition list syntax

2013-02-01T23:01:10Z

T: use built-in definition list syntax

Argentpepper: /* S */ use built-in definition list syntax

2013-02-01T23:00:20Z

S: use built-in definition list syntax

Argentpepper: /* R */ use built-in definition list syntax

2013-01-23T20:46:03Z

R: use built-in definition list syntax

@@ Line 15: / Line 15: @@
 ; circuit : To engineers, a "circuit" is a closed loop.  But in theoretical computer science, a circuit never has loops: instead, it starts with an input, then applies a sequence of simple operations (or gates) to produce an output.  For example, an OR gate outputs 1 if either of its input bits are 1, and 0 otherwise.  The output of a gate can then be used as an input to other gates.
 ; closure : The closure of a set <math>S</math> under some operations, is the set of everything you can get by starting with <math>S</math>, then repeatedly applying the operations.  For instance, the closure of the set <math>\{1\}</math> under addition and subtraction is the set of integers.
-; CNF : Conjunctive Normal Form.  A special kind of Boolean formula, consisting of an AND of ORs of negated or non-negated literals.  For instance: <math>(a\vee\neg b)\wedge(b\vee\neg c\vee d)</math>.  See also [[#dnf|DNF]].
+; <span id="cnf">CNF</span> : Conjunctive Normal Form.  A special kind of Boolean formula, consisting of an AND of ORs of negated or non-negated literals.  For instance: <math>(a\vee\neg b)\wedge(b\vee\neg c\vee d)</math>.  See also [[#dnf|DNF]].
 ; collapse : An infinite sequence (hierarchy) of complexity classes <i>collapses</i> if all but finitely many of them are actually equal to each other.
 ; complement : The complement of a language is the set of all instances not in the language.  The complement of a complexity class consists of the complement of each language in the class.  (Not the set of all languages not in the class!)
@@ Line 22: / Line 22: @@
 ===== D =====
-; decision problem : A problem for which the desired answer is a single bit (1 or 0, yes or no).  For simplicity, theorists often restrict themselves to talking about decision problems.
+; <span id="decision-problem">decision problem</span> : A problem for which the desired answer is a single bit (1 or 0, yes or no).  For simplicity, theorists often restrict themselves to talking about decision problems.
 ; decision tree : A (typically) binary tree where each non-leaf vertex is labeled by a query, each edge is labeled by a possible answer to the query, and each leaf is labeled by an output (typically yes or no).  A decision tree represents a function in the obvious way.
 ; decision tree complexity : Given a Boolean function <math>f:\{0,1\}^n\to\{0,1\}</math>, the decision tree complexity <math>D(f)</math> of <math>f</math> is the minimum height of a decision tree representing <math>f</math> (where height is the maximum length of a path from the root to a leaf).  Also called deterministic query complexity.
 ; depth : When referring to a circuit, the maximum number of gates along any path from an input to the output.  (Note that circuits never contain loops.)
 ; deterministic : Not randomized.
-; DNF : Disjunctive Normal Form.  A Boolean formula consisting of an OR and ANDs of negated or non-negated literals.  For instance: <math>(a\wedge c)\vee(b\wedge\neg c)</math>.  See also [[#cnf|CNF]].
+; <span id="dnf">DNF</span> : Disjunctive Normal Form.  A Boolean formula consisting of an OR and ANDs of negated or non-negated literals.  For instance: <math>(a\wedge c)\vee(b\wedge\neg c)</math>.  See also [[#cnf|CNF]].
-; downward self-reducible : A problem is downward self-reducible if an oracle for instances of size <math>n-1</math> enables one to solve instances of size <math>n</math>.
+; <span id="downward-self-reducible">downward self-reducible</span> : A problem is downward self-reducible if an oracle for instances of size <math>n-1</math> enables one to solve instances of size <math>n</math>.
 ===== E =====
@@ Line 54: / Line 54: @@
 ===== L =====
-; language : Another term for [[#D|decision problem]] (but only a total decision problem, not a promise decision problem).  An instance is in a language, if and only if the answer to the decision problem is "yes."
+; <span id="language">language</span> : Another term for [[#D|decision problem]] (but only a total decision problem, not a promise decision problem).  An instance is in a language, if and only if the answer to the decision problem is "yes."
 : An alternate characterization of a language is as a set of [[#word|words]] over an alphabet <math>\Sigma</math>: <math>L\subseteq \Sigma^*</math>. This is equivalent since determining membership in <math>L</math> is a decision problem called the characteristic function of <math>L</math>. A simple example of a language is ODD, the set of all strings over <math>\{0,1\}</math> which end in 1.
 ; Las Vegas algorithm : A zero-error randomized algorithm, i.e. one that always returns the correct answer, but whose running time is a random variable.  The term was introduced by Babai in 1979.  Contrast with Monte Carlo.
@@ Line 95: / Line 95: @@
 ; random access : This means that an algorithm can access any element x<sub>i</sub> of a sequence immediately (by just specifying i).  It doesn't have to go through x<sub>1</sub>,...,x<sub>i-1</sub> first.  Note that this has nothing directly to do with randomness.
 ; randomized : Making use of randomness (as in 'randomized algorithm').  This is probably an unfortunate term, since it doesn't imply that one starts with something deterministic and then 'randomizes' it.  See also Monte Carlo and Las Vegas.
-; random self-reducible : A problem is random self-reducible if the ability to solve a large fraction of instances enables one to solve <i>all</i> instances.  For example, the discrete logarithm problem is random self-reducible.
+; <span id="random-self-reducible">random self-reducible</span> : A problem is random self-reducible if the ability to solve a large fraction of instances enables one to solve <i>all</i> instances.  For example, the discrete logarithm problem is random self-reducible.
 ; reduction : A result of the form, "Problem A is at least as hard as Problem B."  This is generally shown by giving an algorithm that transforms any instance of Problem B into an instance of Problem A.
 ; relativize : To add an oracle.  We say a complexity class inclusion (or technique) is <i>relativizing</i> if it works relative to all oracles.  Since there exist oracles A,B such that {{zcls|p|p}}<sup>A</sup> = {{zcls|n|np}}<sup>A</sup> and {{zcls|p|p}}<sup>B</sup> does not equal {{zcls|n|np}}<sup>B</sup> {{zcite|BGS75}}, any technique that resolves {{zcls|p|p}} versus {{zcls|n|np}} will need to be nonrelativizing.
@@ Line 126: / Line 126: @@
 ===== W =====
 ; with high probability (w.h.p.) : Usually this means with probability at least 2/3 (or any constant greater than 1/2).  If an algorithm is correct with 2/3 probability, one can make the probability of correctness as high as one wants by just repeating several times and taking a majority vote.<br><i>Note</i>: Sometimes people say "high probability" when they mean "non-negligible probability."
-; word : Given an [[#alphabet|alphabet]] <math>\Sigma</math>, a word is a string <math>w \in \Sigma^*</math>. That is, a string of characters drawn from <math>\Sigma</math>. Using the alphabet <math>\Sigma = \{a, b, \dots, z\}</math>, some valid words include <math>word</math>, <math>science</math>, <math>foobar</math> and <math>fotmewwi</math>.
+; <span id="word">word</span> : Given an [[#alphabet|alphabet]] <math>\Sigma</math>, a word is a string <math>w \in \Sigma^*</math>. That is, a string of characters drawn from <math>\Sigma</math>. Using the alphabet <math>\Sigma = \{a, b, \dots, z\}</math>, some valid words include <math>word</math>, <math>science</math>, <math>foobar</math> and <math>fotmewwi</math>.
 ===== X =====

@@ Line 5: / Line 5: @@
 ===== B =====
-; block sensitivity : Given a Boolean function <math>f:\{0,1\}^n\to\{0,1\}</math>, the block sensitivity <math>\mathrm{bs}^X(f)</math> of an input <math>X=x_1\dots x_n</math> is the maximum number of disjoint blocks <math>B</math> of variables such that <math>f(X)</math> does not equal <math>f\left(X^{(B)}\right)</math>, where <math>X^{(B)}</math> denotes <math>X</math> with the variables in <math>B</math> flipped.  Then <math>\mathrm{bs}(f)</math> is the maximum of <math>\mathrm{bs}^X(f)</math> over all <math>X</math>.  Defined by Nisan in 1991.  See also [[#sensitivity|sensitivity]], [[#certificate-complexity|certificate complexity]].
+; <span id="block-sensitivity">block sensitivity</span> : Given a Boolean function <math>f:\{0,1\}^n\to\{0,1\}</math>, the block sensitivity <math>\mathrm{bs}^X(f)</math> of an input <math>X=x_1\dots x_n</math> is the maximum number of disjoint blocks <math>B</math> of variables such that <math>f(X)</math> does not equal <math>f\left(X^{(B)}\right)</math>, where <math>X^{(B)}</math> denotes <math>X</math> with the variables in <math>B</math> flipped.  Then <math>\mathrm{bs}(f)</math> is the maximum of <math>\mathrm{bs}^X(f)</math> over all <math>X</math>.  Defined by Nisan in 1991.  See also [[#sensitivity|sensitivity]], [[#certificate-complexity|certificate complexity]].
 ; Blum integer : A product of two distinct primes, both of which are congruent to 3 mod 4.
 ; Boolean formula : A circuit in which each gate has fanout 1.
@@ Line 11: / Line 11: @@
 ===== C =====
-; certificate complexity : Given a Boolean function <math>f:\{0,1\}^n\to\{0,1\}</math>, the certificate complexity <math>C^X(f)</math> of an input <math>X=x_1\dots x_n</math> is the minimum size of a set <math>S</math> of variables such that <math>f(Y)=f(X)</math> whenever <math>Y</math> agrees with <math>X</math> on every variable in <math>S</math>.  Then <math>C(f)</math> is the maximum of <math>C^X(f)</math> over all <math>X</math>.  See also [[#block-sensitivity|block sensitivity]].
+; <span id="certificate-complexity">certificate complexity</span> : Given a Boolean function <math>f:\{0,1\}^n\to\{0,1\}</math>, the certificate complexity <math>C^X(f)</math> of an input <math>X=x_1\dots x_n</math> is the minimum size of a set <math>S</math> of variables such that <math>f(Y)=f(X)</math> whenever <math>Y</math> agrees with <math>X</math> on every variable in <math>S</math>.  Then <math>C(f)</math> is the maximum of <math>C^X(f)</math> over all <math>X</math>.  See also [[#block-sensitivity|block sensitivity]].
 [[Image:Example-circuit.jpg|thumb|200px|right|Example of a Boolean [[#circuit|circuit]] of [[#depth|depth]] 4 that checks if two 2-bit strings are different.]]
 ; circuit : To engineers, a "circuit" is a closed loop.  But in theoretical computer science, a circuit never has loops: instead, it starts with an input, then applies a sequence of simple operations (or gates) to produce an output.  For example, an OR gate outputs 1 if either of its input bits are 1, and 0 otherwise.  The output of a gate can then be used as an input to other gates.

@@ Line 1: / Line 1: @@
 ===== A =====
 ; adaptive : Each question you ask (say to an oracle) can depend on the answers to the previous questions.  If A and B are complexity classes, then A<sup>B</sup> is the class of languages decidable by an A machine that can make adaptive queries to a B oracle.
-; alphabet : Typically denoted <math>\Sigma</math>, an alphabet is a finite set of characters. Common examples include <math>\{a, b, \dots, z\}</math> and <math>\{0, 1\}</math>.
+; <span id="alphabet">alphabet</span> : Typically denoted <math>\Sigma</math>, an alphabet is a finite set of characters. Common examples include <math>\{a, b, \dots, z\}</math> and <math>\{0, 1\}</math>.
 ; asymptotic : Concerning the rate at which a function grows, ignoring constant factors.  For example, if an algorithm uses 3n+5 steps on inputs of size n, we say its running time is "asymptotically linear" - emphasizing that the linear dependence on n is what's important, not the 3 or the 5.

@@ Line 131: / Line 131: @@
 ===== Y =====
 ===== Z =====
-; <span id=zeroone-law>zero-one law</span> : Any theorem which specifies that the probability of an event is either zero or one is known as a zero-one law.
+; <span id="zeroone-law">zero-one law</span> : Any theorem which specifies that the probability of an event is either zero or one is known as a zero-one law.

@@ Line 131: / Line 131: @@
 ===== Y =====
 ===== Z =====
-{{Term|id=zeroone-law|zero-one law|Any theorem which specifies that the probability of an event is either zero or one is known as a zero-one law.}}
+; <span id=zeroone-law>zero-one law</span> : Any theorem which specifies that the probability of an event is either zero or one is known as a zero-one law.

@@ Line 120: / Line 120: @@
 ===== U =====
-<font color="red"><b>unary:</b></font> An inefficient encoding system, in which the integer n is denoted by writing n 1's in sequence.
+; unary : An inefficient encoding system, in which the integer n is denoted by writing n 1's in sequence.
+; uniform : A single algorithm is used for all input lengths.  For example, Turing machines are a uniform model of computation -- one just has to design a single Turing machine for multiplication, and it can multiply numbers of any length.  (Contrast with the circuit model.)
-<font color="red"><b>uniform:</b></font> A single algorithm is used for all input lengths.  For example, Turing machines are a uniform model of computation -- one just has to design a single Turing machine for multiplication, and it can multiply numbers of any length.  (Contrast with the circuit model.)
+; upper bound : A result showing that a function grows <i>at most</i> at a certain asymptotic rate.  For example, any algorithm for a problem yields an upper bound on the complexity of the problem.
 ===== W =====

@@ Line 111: / Line 111: @@
 ===== T =====
-<font color="red"><b>tape:</b></font> The memory used by a Turing machine.
+; tape : The memory used by a Turing machine.
+; &Theta; (Theta) : For a function <math>f(n)</math> to be <math>\Theta(g(n))</math> means that <math>f(n) = O(g(n))</math> and <math>f(n) = \Omega(g(n))</math> (i.e. they grow at the same rate).
-<font color="red"><b>&Theta; (Theta):</b></font> For a function <math>f(n)</math> to be <math>\Theta(g(n))</math> means that <math>f(n) = O(g(n))</math> and <math>f(n) = \Omega(g(n))</math> (i.e. they grow at the same rate).
+; tight bound : An upper bound that matches the lower bound, or vice versa.  I.e. the best possible bound for a function.
+; total : A total function is one that is defined on every possible input.
-<font color="red"><b>tight bound:</b></font> An upper bound that matches the lower bound, or vice versa.  I.e. the best possible bound for a function.
+; truth table : A table of all <math>2^n</math> possible inputs to a Boolean function, together with the corresponding outputs.
+; truth table reduction : A Turing reduction in which the oracle queries must be nonadaptive.
-<font color="red"><b>total:</b></font> A total function is one that is defined on every possible input.
+; Turing reduction : A reduction from problem A to problem B, in which the algorithm for problem A can make queries to an oracle for problem B.  (Contrast with many-one reduction.)
 ===== U =====

@@ Line 100: / Line 100: @@
 ===== S =====
-<font color="red"><b>satisfiability (SAT):</b></font> One of the central problems in computer science.  The problem is, given a Boolean formula, does there exist a setting of variables that <i>satisfies</i> the formula (that is, makes it evaluate to true)?  For example, <math>(a\vee b)\wedge(\neg a\vee\neg b)</math> is satisfiable: <math>a=\mathrm{true}</math>, <math>b=\mathrm{false}</math> and <math>a=\mathrm{false}</math>, <math>b=\mathrm{true}</math> are both satisfying assignments.  But <math>(a\vee b) \wedge (\neg a) \wedge (\neg b)</math> is unsatisfiable. ''See also'': [[Complexity Garden#sat|Garden entry on satisfiability]].
+; satisfiability (SAT) : One of the central problems in computer science.  The problem is, given a Boolean formula, does there exist a setting of variables that <i>satisfies</i> the formula (that is, makes it evaluate to true)?  For example, <math>(a\vee b)\wedge(\neg a\vee\neg b)</math> is satisfiable: <math>a=\mathrm{true}</math>, <math>b=\mathrm{false}</math> and <math>a=\mathrm{false}</math>, <math>b=\mathrm{true}</math> are both satisfying assignments.  But <math>(a\vee b) \wedge (\neg a) \wedge (\neg b)</math> is unsatisfiable. ''See also'': [[Complexity Garden#sat|Garden entry on satisfiability]].
+; self-reducible : A problem is self-reducible if an oracle for the decision problem enables one to solve the associated function problem efficiently.  For example, {{zcls|n|npc|NP-complete}} problems are self-reducible.  See also: [[#downward-self-reducible|downward self-reducible]], [[#random-self-reducible|random self-reducible]].
-<font color="red"><b>self-reducible:</b></font> A problem is self-reducible if an oracle for the decision problem enables one to solve the associated function problem efficiently.  For example, {{zcls|n|npc|NP-complete}} problems are self-reducible.  See also: [[#downward-self-reducible|downward self-reducible]], [[#random-self-reducible|random self-reducible]].
+; <span id="sensitivity">sensitivity</span> : Given a Boolean function {{bfunc}}, the sensitivity <math>s^X(f)</math> of an input <math>X=x_1\dots x_n</math> is the number of variables such that flipping them changes the value of <math>f(X)</math>.  Then <math>s(f)</math> is the maximum of <math>s^X(f)</math> over all <math>X</math>.
+; size : When referring to a string, the number of bits.  When referring to a circuit, the number of gates.
-<font color="red" id="sensitivity"><b>sensitivity:</b></font> Given a Boolean function {{bfunc}}, the sensitivity <math>s^X(f)</math> of an input <math>X=x_1\dots x_n</math> is the number of variables such that flipping them changes the value of <math>f(X)</math>.  Then <math>s(f)</math> is the maximum of <math>s^X(f)</math> over all <math>X</math>.
+; space : The amount of memory used by an algorithm (as in space complexity).
+; STOC : ACM Symposium on Theory of Computing (held every spring).
-<font color="red"><b>size:</b></font> When referring to a string, the number of bits.  When referring to a circuit, the number of gates.
+; string : A sequence of 1s and 0s.  (See, it's not just physicists who plumb Nature's deepest secrets -- we computer scientists theorize about strings as well!)<br><i>Note</i>: For simplicity, one usually assumes that every character in a string is either 1 or 0, but strings over larger alphabets can also be considered.
+; subexponential : Growing slower (as a function of n) than any exponential function.  Depending on the context, this can either mean <math>2^{o(n)}</math> (so that the Number Field Sieve factoring algorithm, which runs in about <math>2^{n^{1/3}}</math> time, is "subexponential"); or <math>2^{o(n^{\epsilon})}</math> for every <math>\epsilon>0</math>.
-<font color="red"><b>space:</b></font> The amount of memory used by an algorithm (as in space complexity).
+; superpolynomial : Growing faster (as a function of <math>n</math>) than any polynomial in <math>n</math>.  This is <i>not</i> the same as exponential: for example, <math>n^{\log n}</math> is superpolynomial, but not exponential.
 ===== T =====