Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Previous Chapter

Series

Index

$bindex-math-0001$
$bindex-math-0002$
$bindex-math-0003$
$bindex-math-0004$
$bindex-math-0005$
$bindex-math-0006$
$bindex-math-0007$
$bindex-math-0008$
$bindex-math-0009$
$bindex-math-0010$
$bindex-math-0011$
$bindex-math-0012$
$bindex-math-0013$
$bindex-math-0014$
$bindex-math-0015$
$bindex-math-0016$
$bindex-math-0017$
$bindex-math-0018$
$bindex-math-0019$
$bindex-math-0020$
$bindex-math-0021$
$bindex-math-0022$
$bindex-math-0023$
$bindex-math-0024$
$bindex-math-0025$
$bindex-math-0026$
$bindex-math-0027$
$bindex-math-0028$
$bindex-math-0029$
$bindex-math-0030$
$bindex-math-0031$ -completeness
$bindex-math-0032$
$bindex-math-0033$
$bindex-math-0034$
$bindex-math-0035$ -completeness
$bindex-math-0036$
$bindex-math-0037$
$bindex-math-0038$
$bindex-math-0039$
$bindex-math-0040$
$bindex-math-0041$
#HC
$bindex-math-0043$
$bindex-math-0044$
$bindex-math-0045$ -complete function
#SAT
#SS
$bindex-math-0048$ -SAT
#VC
$bindex-math-0050$
$bindex-math-0051$
$bindex-math-0052$
$bindex-math-0053$ -acceptance
A-reducibility
Aanderaa
$bindex-math-0055$
$bindex-math-0056$
adjacency matrix
1. eigenvalue
Adleman, L.
adversary argument
affine subspace
Aho, A.
Aiello, W.
Ajtai, M.
algebraic criterion
almost-NP
almost one-to-one function
almost-P
Alon, N.
alphabet
alternating tree
alternating Turing machine (ATM)
1. accepting computation subtree
2. existential configuration
3. existential state
4. polynomial-time
5. universal configuration
6. universal state
AM
AM $bindex-math-0057$
AM $bindex-math-0058$
AM hierarchy
AM2 circuit
AM2 CIRCUIT VALUE
amplification of accepting probability
AP-reduction
APPROX-BP
APPROX-GCOLOR
APPROX-KS
APPROX-SCS
approximation, see also c-approximation and

r-APPROX-Π

ratio
to a counting function
to an optimization problem
to TSP

approximation scheme, polynomial-time (PTAS)
1. fully (FPTAS)
2. fully probabilistic
arithmetic hierarchy
Arora, S.
Arthur machine
Arthur-Merlin proof system
Arvind, V.
ASPACE $bindex-math-0063$
assignment, see Boolean assignment
assignment tester
assignment testing proof system
ATIME $bindex-math-0064$
ATM, see alternating Turing machine
$bindex-math-0065$
automata theory
automorphism
1. orbit of an
axiomatizable theory
1. sound
2. theorem
B
$bindex-math-0067$
b-terminal
Babai, L.
Bach, E.
Baker, T.
Balcázar, J.
Barrington, D.
Beals, R.
Beame, C.
Beigel, R.
Belanger, J.
Bellare, M.
Bennett, C.
Ben-Or, M.
Berkowitz, S. J.
Berlekamp, E.
Berman, L.
Berman, P.
Berman-Hartmanis Isomorphism Conjecture
1. EXP version
Bern, M.
Bernstein, E.
Bernstein-Schröder-Cantor Theorem
Best, M. R.
BFG, see BOOLEAN FORMULA GAME
BH
BHP, see BOUNDED HALTING PROBLEM
bi-immune set, 271; see also strongly bi-immune set
1. relative
BIN PACKING (BP)
binary tree
binomial distribution
bipartite graph
bipartite graph property
blank symbol $bindex-math-0070$
BLR test, see Blum–Luby–Rubinfeld test
Blum, A.
Blum, L.
Blum, M.
Blum, N.
Blum–Luby–Rubinfeld test
Blum's Speed-up Theorem
Bollobas, B.
Book, R.
Boolean assignment
1. invariant
2. partial
3. truth
Boolean circuit
1. AM2
2. depth
3. encoding of a
4. fan-in
  1. bottom
5. generated by a DTM
6. interpreter
7. levelable
8. logical gates
9. monotone
10. planar
11. polynomial-size
12. random
13. size
Boolean formula
1. bounded variable
2. clause
3. conjunctive normal form
4. disjunctive normal form
5. quantified, see quantified Boolean formula
6. r-unsatisfiable
7. 3-CNF
8. 3-DNF
BOOLEAN FORMULA GAME (BFG)
Boolean function
1. contravariant of a
2. dual of a
3. elusive
4. graph property
5. monotone
6. restriction of a
  1. random
7. symmetric
8. symmetric permutation
9. trivial
10. weakly symmetric
Boolean hierarchy
BOOLEAN MATRIX MULTIPLICATION
Boppana, R.
Borel field
Borel set
Borodin, A.
BOUNDED HALTING PROBLEM (BHP)
1. relativized
bounded variable, in a Boolean formula
BP, see BIN PACKING
$bindex-math-0072$
BP-operator
BPP
BPP $bindex-math-0074$
BPP $bindex-math-0075$
BPP machine, universal
BPP Theorem
1. generalized
branching program
1. bounded-width
2. permutation
3. σ-computation
Brightwell, G.
Broder, A. Z.
Buss, J.
BUSY BEAVER
1. time-bounded version
$bindex-math-0077$
$bindex-math-0078$
$bindex-math-0079$
$bindex-math-0080$
$bindex-math-0081$
$bindex-math-0082$
c-approximation, by a Boolean circuit
$bindex-math-0084$ -hard problem
Cai, J.-Y.
Cantor, G.
Cantor space
Carter, J. L.
Cauchy–Schwartz inequality
CC
census function
certificate
CFL
CG-SAT, see CONSTRAINT GRAPH SATISFIABILITY
Chandra, A.
characteristic function
characteristic sequence, of a set
$bindex-math-0085$
$bindex-math-0086$
Christofides, N.
Church-Turing Thesis
1. extended
circuit, see Boolean circuit
circuit size complexity
CIRCUIT VALUE PROBLEM (CVP)
class, see complexity class and language class
clause
1. prime
2. size of a
clique
CLIQUE
CLIQUE $bindex-math-0087$
clique indicator
(CLIQUE, r-NOCLIQUE)
clocked machine, see Turing machine
CNF, see conjunctive normal form
Cobham, A.
coding
Coffman, E.
collapsing degree
COMPARATOR CIRCUIT VALUE
comparator gate
complementary predicates
1. $bindex-math-0089$ -
2. $bindex-math-0090$ -
3. $bindex-math-0091$ -
completeness
complexity core, polynomial-time
complexity measure; see also Kolmogorov complexity, and time complexity measure
1. ogarithmic
complexity class
1. nonuniform
2. uniform
computable function (language)
1. feasibly
2. partial
computable real number, see real number
computational model
1. nondeterministic
2. nonuniform
3. probabilistic
4. reasonable
concatenation,
1. of strings
2. of languages
Condon, A.
configuration
1. existential, of an ATM
2. game
  1. losing
3. initial
4. of an oracle DTM
5. of a Merlin machine
6. of a PTM
conjunction
conjunctive normal form (CNF)
coNP
const
constraint graph
1. alphabet reduction
2. degree-regularization
3. expanderization
4. gap amplification
5. power graph
  1. t-step path
CONSTRAINT GRAPH SATISFIABILITY (CG-SAT)
context-free language
contrastar
contravariant
convex hull
Cook, S.
Cook's Theorem
Cormen, T. H.
coRP
countable set
counting problem
1. approximation to a
2. polynomial-time computable
Cramer's rule
creative set, see p-creative set and
k-creative set
Crescenzi, P.
CRITICAL HC
cryptography
$bindex-math-0095$
$bindex-math-0096$
Csansky, L.
CVP, see CIRCUIT VALUE PROBLEM
cycle
cycle cover
cylinder
$bindex-math-0097$
$bindex-math-0098$
$bindex-math-0099$
Daley, R.
de Morgan's law
decision problem
1. partial
decision tree
1. depth
2. randomized, see randomized decision tree
3. child node
4. parent node
decision tree complexity
decisive characterization, of BPP
1. of RP
degree
1. collapsing
2. iso-
delayed diagonalization
Δ
$bindex-math-0101$
$bindex-math-0102$
$bindex-math-0103$
δ
δ-close
δ-far
DeMoive-Laplace Limit Theorem
density
1. subexponential
derandomization
$bindex-math-0107$
determinant,
1. of an integer matrix
2. of a polynomial matrix
DETERMINANT OF A POLYNOMIAL MATRIX (DPM)
DETERMINISTIC FINITE AUTOMATA INTERSECTION (DFA-INT)
determinisitic Turing machine (DTM), see Turing machine
Deutsch, D.
DFA-INT, see DETERMINISTIC FINITE AUTOMATA INTERSECTION
DGISO
diagonalization
1. delayed
2. stage construction
Diffie, W.
digital signature
digraph
1. loop in a
dimension, of a face
Dinur, I.
directed graph, see digraph
disjunction
disjunctive normal form (DNF)
Distance Lemma
1. second
DNF, see disjunctive normal form
DP
$bindex-math-0108$
DPM, see DETERMINANT OF A POLYNOMIAL MATRIX
$bindex-math-0109$
$bindex-math-0110$
DTM, see Turing machine, deterministic
Du, D.-Z.
Du, X.
dual
Dunne, P. E.
dynamic programming
edge
edge expansion
Edmonds, J.
elementary collapse
elementary product
elementary sum
Elgot, C. C.
elusiveness
empty string
enumerable set
Erdös-Rado Sunflower Lemma
$bindex-math-0111$
error probability, of a PTM
Euclidean graph
Euler characteristic
Euler function
Eulerian circuit
Eulerian circuit problem
Eulerian graph
Euler's criterion
Even, S.
EXACT CLIQUE
EXACT-TSP
exclusive-or
EXP
EXP-BHP, see EXPONENTIAL-TIME BOUNDED HALTING PROBLEM
EXP-complete set
EXP-CVP, see EXPONENTIAL-SIZE CIRCUIT VALUE PROBLEM
EXP-SAT
expander
1. $bindex-math-0112$ -
2. Lubotzky–Hillip–Sarnak
3. Marguli–Gaber–Galil
$bindex-math-0113$
EXPONENTIAL-SIZE CIRCUIT VALUE PROBLEM (EXP-CVP)
EXPONENTIAL-TIME BOUNDED HALTING PROBLEM (EXP-BHP)
exponentiation, modulo an integer
EXPSPACE
EXPSPACE-complete set
Extended Church-Turing Thesis
EXTRATING A BIT
$bindex-math-0114$
$bindex-math-0115$
$bindex-math-0116$
$bindex-math-0117$
$bindex-math-0118$
face
1. dimension
2. free
3. maximal
FACTOR, see INTEGER FACTORING
false $bindex-math-0119$
fan-in
FBPP $bindex-math-0120$
$bindex-math-0121$
feasible subgraph
feasibly computable problem
Feather, T.
Feige, U.
Fenner, S.
FewP
finite-to-one function
Fischer, M.
fixed point
Fixed Point Theorem
1. Lefshetz’
flow, of a network
Fortnow, L.
Fortune, S.
FP
$bindex-math-0123$
$bindex-math-0124$
FPSPACE
FPTAS, see approximation scheme
Friedman, H.
Frieze, A. M.
fully polynomial-time approximation scheme (FPTAS)
fully probabilistic polynomial-time approximation scheme
fully space-constructibility
fully time-constructibility
function, see also Boolean function
1. length-increasing
2. partial
3. super-polynomial
4. total
Fürer, M.
Furst, M.
GACC, see GRAPH ACCESSIBILITY
Gacs, P.
Galois field
game, see two-person game
Gao, S.-X.
gap amplification
GAP CONSTRAINT GRAPH SATISFIABILITY
Garey, M. R.
gate-elimination method
GC, see GRAPH CONSISTENCY
GCOLOR, see GRAPH COLORING
GCOLOR $bindex-math-0125$
GENERAL MATCHING (GM)
Generalized BPP Theorem
GENERALIZED RAMSEY NUMBER (GRN)
GEOGRAPHY
geometric simplicial complex
$bindex-math-0126$
Gill, J.
girth
GISO, see GRAPH ISOMORPHISM
$bindex-math-0127$ , see GRAPH NONISOMORPHISM
GM, see GENERAL MATCHING
Goldman, M.
Goldreich, O.
Goldschlager, L. M.
Goldsmith, J.
Goldwasser, S.
Graham, R. L.
graph(s), 46, 151; see also digraph
1. Boolean function representation
2. clique of a
3. complement
4. connected
5. cubic
6. cycle in a
7. d-regular
8. directed, see digraph
9. edge of a
10. edge expansion
11. Euclidean
12. Eulerian
13. factor-critical
14. girth of a
15. isomorphic
16. k-colored
17. nonplaner
18. path in a
  1. simple
19. planar
20. scorpion
21. vertex cover of a
22. vertex of a
GRAPH ACCESSIBILITY (GACC)
1. undirected graph
GRAPH COLORING (GCOLOR)
GRAPH CONSISTENCY (GC)
GRAPH 3-COLORABILLITY (G3C)
GRAPH ISOMORPHISM (GISO)
GRAPH NONISOMORPHISM ( $bindex-math-0130$ )
graph property
1. bipartite
2. monotone
Greenlaw, R.
GRN, see GENERALIZED RAMSEY NUMBER
Grollman, J.
group
G3C, see GRAPH 3-COLORABILITY
guess-and-verify algorithm
$bindex-math-0131$
$bindex-math-0132$
Halldórsson, M.
$bindex-math-0133$
halting probability, of a PTM
halting problem
1. relativized
HAMILTONIAN CIRCUIT (HC)
1. paddability
Hamiltonian circuit
Hamming distance
hardness
Hartmanis, J.
hashing function
1. linear
  1. random
2. universal
Håstad, J.
HC, see HAMILTONIAN CIRCUIT
Heller, H.
Hellman, M.
Hemachandra, L. A.,
HEX
high hierarchy
1. relativized
Holt, R. C.
Homer, S.
Hoory
Hopcroft, J.
Hopf index formula
Hu, X.-D.
Huang, M. A.
Hunt, H. B. III
Ibarra, O. H.
IEE, see INTEGER EXPRESSION EQUIVALENCE
Illies, N.
Immerman, N.
immune set
implicant
1. prime
independence results
INDEPENDENT SET (IS)
independent set
inner product
integer expression
INTEGER EXPRESSION EQUIVALENCE (IEE)
INTEGER FACTORING (FACTOR)
INTEGER PROGRAMMING (IP)
interactive proof system
1. multi-prover
2. probabilistic
interactive protocol
1. k-prover
interactive Turing machine
invariant assignment, of a symmetric permutation
inverter
invertible function, polynomial-time
invertible reducibility, polynomial-time
ι
IP, see Integer Programming
IP
IP $bindex-math-0136$
IP $bindex-math-0137$
IS, see INDEPENDENT SET
IS-b
$bindex-math-0139$
iso-degree
Isolation Lemma
isomorphism, polynomial-time
isomorphism type
Jerrum, M. R.
Jiang, T.
Johnson, D.
join
Joseph, D.
Joseph-Young Conjecture
1. EXP version
K
$bindex-math-0141$
$bindex-math-0142$
k-colored graph
k-creative set
k-truth-table reducibility, polynomial-time
k-UP
Kahn, J.
Kannan, S.
Karloff, H.
Karmarkar, N.
Karp, R. M.
Karp conjecture
Khachiyan, L.
Khanna, S.
Killian, J.
Kim, C. E.
King, V.
Kirkpatrick, D.
Kiwi, M.
Kleene, S. C.
Kleene closure
Kleitman, D. J.
KNAPSACK (KS)
Ko, K.
Köbler, J.
Kolmogorov, A. N.
Kolmogorov complexity
Kozen, D.
Kranakis, E.
KS, see KNAPSACK
Kuratowski's Theorem
Kurtz, S.
Kwiatkowski, D. J.
$bindex-math-0147$
$bindex-math-0148$
$bindex-math-0149$
$bindex-math-0150$
$bindex-math-0151$
L-reduction
Ladner, R.
λ
$bindex-math-0154$
Landau, S.
language
1. computable
2. concatenation of
3. context-sensitive
4. recursive
5. recursively enumerable (r.e.)
language class
Laplace expansion
Laplante, S.
Lautemann, C.
Law of Quadratic Reciprocity
Lawler, E. L.
LE
Lebesgue measure
Lefshetz’ Fixed Point Theorem
Legendre symbol
Legendre-Jacobi symbol
length-increasing function
levelable circuit
Levin, L.
Lewis, P. M.
lexicographic ordering
Li, M.
Lin, C.-L.
linear congruence generator, see pseudorandom generator
linear extension
linear programming
Linear Speed-up Theorem
link
Lipton, R. J.
literal
Liu, C. L.
log
log-space uniformity
LOGCFL
LOGSPACE
Long, T.
LONGEST DIRECT CIRCUIT
LONGEST PATH (LP)
Lovász, L.
low hierarchy
1. relativized
Loxton, J. H.
LP, see LONGEST PATH
Lund, C., 80, 406, 455–457
Lupanov, O. B.
Lynch, N.
M
$bindex-math-0156$
$bindex-math-0157$
$bindex-math-0158$
$bindex-math-0159$
$bindex-math-0160$
MA $bindex-math-0161$
Mahaney, S.
Maier, D.
MAJ
majority quantifier
majority vote
MAJSAT
Manders, K.
many-one reducibility
1. log-space
2. $bindex-math-0162$
3. polynomial-time
matching
MAX-CLIQUE
MAX-SNP
MAX-SNP-completeness
maximal subset
maximum satisfiability problem
Mayr, E. W.
McKenzie, P.
McMillan's Theorem
MCV, see MONOTONE CIRCUIT VALUE
Merlin machine
1. accepting probability
2. configuration
Meyer, A.
Micali, S.
Miller, G.
Milner, E. C.
MIN-BISECTION
MIN-NFA, see MINIMAL NONDETERMINISTIC FINITE AUTOMATON
MIN-TSP
MINIMAL NONDETERMINISTIC FINITE AUTOMATON (MIN-NFA)
minimax
MINIMAX-CIRCUIT
MINIMAX-CLIQUE
MINIMAX-3DM
minimum matching problem
minimum spanning tree problem
minterm
MIP
Mitchell, J.
MOD $bindex-math-0163$ function
monoid
monotone circuit
MONOTONE CIRCUIT VALUE (MCV)
Moore, D.
Moran, S.
Motwani, R.
μ
$bindex-math-0165$
Mulmuley, K.
multiplication
1. of integers
2. of permutations
Myhill, J.
$bindex-math-0166$ -expander
NAND CIRCUIT VALUE
NAND gate
NC
1. reducibility
$bindex-math-0168$ , 223,
$bindex-math-0169$
$bindex-math-0170$
Neciporuk, E. I.
negation
negligibility
network
1. flow
NEXP
NEXP-complete set
NEXP
Nick's class
Nisan, N.
NLOGSPACE
NLOGSPACE-complete set
nonadaptive proof system
nondeterministic Turing machine (NTM), 14; see also Turing machine
1. accepting a string
2. accepting path
3. computation
4. computing a function
5. halting path
6. k-ambiguous
7. oracle, see oracle nondeterministic Turing machine
8. output
9. unambiguous
10. universal
nonuniform complexity class
nonuniform- $bindex-math-0174$
nonuniform-NC
nonuniform- $bindex-math-0176$
nonuniform- $bindex-math-0177$
nonuniform- $bindex-math-0178$
normal subgroup
NOT-ALL-EQUAL-3SAT
NP
1. characterization of
  1. PCP
2. enumeration of
NP $bindex-math-0179$
NP $bindex-math-0180$
NP $bindex-math-0181$
NP $bindex-math-0182$
NP/poly
NP $bindex-math-0183$
NP-complete set
1. natural
NPSPACE
NSPACE $bindex-math-0184$
NTIME $bindex-math-0185$
NTM, see nondeterministic Turing machine
ODD MAXIMUM FLOW (OMF)
Ogihara, M.
Ogiwara, M.
Oliver, R.
$bindex-math-0186$
$bindex-math-0187$
OMF, see ODD MAXIMUM FLOW
1-factor
1-IN-3-3SAT
$bindex-math-0189$ GAP-3SAT
$bindex-math-0190$ GAP-CG-SAT, see GAP CONSTRAINT GRAPH SATISFIABILITY
one-one reducibility, polynomial-time, 254; see also invertible reducibility
one-sided error
one-way function
1. characterization
2. k-to-one
3. length-increasing
4. strong
5. trapdoor
6. weak
optimization problem
1. approximation to an, see approximation
2. NP-hard
3. solution
  1. value of a
oracle
1. function
2. random
3. set
oracle class
oracle nondeterministic Turing machine, 82; see also oracle Turing machine
1. answer state
2. polynomial-time
3. query state
4. query tape
oracle probabilistic Turing machine, 321; see also oracle Turing machine
1. nonadaptive
ORACLE-SAT
oracle Turing machine
1. answer state
2. computation
3. function oracle
4. polynomial-time
5. positive
6. query state
7. query string
8. query tape
9. robust
10. set oracle
orbit
1. center of gravity
Orponen, P.
P
1. enumeration of
$bindex-math-0192$
$bindex-math-0193$
$bindex-math-0194$
$bindex-math-0195$
P/log
P/poly
¶-bi-immune set
¶-complete set
p-creative set,
1. for NP
2. for P
P-immune set
p-isomorphic sets
p-selective set
paddable set
1. length-increasingly
2. weakly
padding function
pairing function
Panconesi, A.
Papadimitriou, C. H.
parallel computation
parallel random access machine (PRAM)
PARITY
$bindex-math-0199$
parity function
parity machine
parity operator
PARITY-CVP
Parseval's Identity
partial assignment
partial computable function
partial decision problem
partial function
partial ordering
1. polynomially related
2. linear extension
partial recursive function
PARTITION
1. paddability
Paterson, M.
path

simple

Paul, W. J.
PCP, 409; see also probabilistic checkable proof systems
PCP $bindex-math-0200$
PCP $bindex-math-0201$
PCV, see PLANAR CIRCUIT VALUE
PERFECT MATCHING (PM)
PEERM
$bindex-math-0202$
permanent,
1. of a Boolean matrix
2. of an integer matrix
permutation,
1. cyclic
2. symmetric
permutation branching program
permutation group
1. transitive subgroup
PH
1. characterization of
  1. PCP
$bindex-math-0203$
$bindex-math-0204$
Π
$bindex-math-0206$
$bindex-math-0207$ -predicate
$bindex-math-0208$ -complete set
Pippenger, N.
planar circuit
PLANAR CIRCUIT VALUE (PCV)
Plassmann, P.
plucking operation
Plumstead, J.
PM, see PERFECT MATCHING
poly
polynomial-size circuit
polynomial-time approximation scheme, see approximation scheme
polynomial-time hierarchy
1. collapsing of
2. PCP characterization of
3. relativized
polynomial-time invertible function
polynomial-time invertible reducibility
polynomial-time isomorphism
polynomially honest function
positive relativization
Post's problem
PP
PP-completeness
PRAM, see parallel random access machine
Pratt, V.
prefix set
$bindex-math-0209$
PRIMALITY TESTING (PRIME)
PRIME, see PRIMALITY TESTING
PRIMESAT
private-key cryptosystem
probabilistic algorithm
probabilistic interactive proof system, see interactive proof system
probabilistic nondeterministic Turing machine
probabilistic quantifier
probabilistic Turing machine (PTM)
1. accepting an input
2. accepting probability
3. configuration
4. equivalence of
5. halting probability
6. random state
7. rejecting probability
8. strong equivalence of
probabilistically checkable proof (PCP) systems
1. weak
program over a monoid
projection, of a Boolean circuit
promise problem
pseudo polynomial-time algorithm
pseudorandom generator
1. linear congruence generator
2. $bindex-math-0210$ -generator
3. quadratic residue generator
4. strongly unpredictable
PSPACE
1. enumeration of
2. characterization of
  1. PCP
PSPACE-complete set
PTAS, see approximation scheme
PTM, see probabilistic Turing machine
public-key cryptosystem
1. ciphertext
2. decryption algorithm
3. decryption key
4. encryption algorithm
5. encryption key
6. plaintext
7. Rivest-Shamir-Adleman (RSA)
QBF, see QUANTIFIED BOOLEAN FORMULA
$bindex-math-0211$
QNR, see QUADRATIC NONRESIDUES
QR, see QUADRATIC RESIDUOSITY
$bindex-math-0212$
$bindex-math-0213$
QUADRATIC NONRESIDUES (QNR)
quadratic residue
quadratic residue generator, see pseudorandom generator
QUADRATIC RESIDUOSITY (QR)
QUANTIFIED BOOLEAN FORMULA (QBF)
1. self-reducibility
quantified Boolean formula
1. normal form
2. 3-CNF
quantifier
1. scope
quantifier changes, of an ATM
quantum Turing machine
query bits
Quicksort,
1. deterministic algorithm
2. randomized algorithm
$bindex-math-0215$
$bindex-math-0216$
$bindex-math-0217$
r-APPROX-CLIQUE
r-APPROX-Π
r-APPROX-3SAT
r-APPROX-TSP
r-degree
r.e., see recursively enumerable language
r-NOCLIQUE
r-UNSAT
Rabin, M.
Rackoff, C.
Radhakrishnan, J.
Raghavan, P.
RAM, see random access machine
random access machine (RAM)
1. complexity measure
random bit(s)
1. generator
2. shared
random circuit
random oracle
random restriction
random walk, in an expander
randomization
randomized algorithm
randomized decision tree
1. expected depth
2. expected time
randomized decision tree complexity
randomized reduction
rank, of a matrix
Ravikumar, B.
Rayleigh quotient
Raz, R.
Razborov, A. A.
$bindex-math-0226$
real number,
1. computable
  1. binary
  2. Cauchy
  3. Dedekind
  4. Turing
2. polynomial-time computable,
  1. binary
  2. Cauchy
  3. Dedekind
recursion theory
recursive function (language)
1. partial
recursive function theory
recursively enumerable (r.e.) language
reducibility, 49; see also many-one reducibility,
1. one-one reducibility, strong NP reducibility, truth-table reducibility and Turing reducibility
2. adaptive
3. closed under
4. conjunctive, see truth-table reducibility
5. disjunctive, see truth-table reducibility
6. NC
7. polynomial-time invertible
regular expression
1. extended
Reingold, E. M.
Reingold, N.
Reingold, O.
$bindex-math-0227$
relativization
1. positive
restriction
1. random
Rice, H.
Rivest, R.
Rivest-Shamir-Adleman cryptosystem (RSA)
RNC
Rogers, H. Jr.
Rogers, J.
Roman, S.
Rosenberg, A. L.
RP
$bindex-math-0228$
RSA cryptosystem, see Rivest-Shamir-Adleman cryptosystem
RTIME $bindex-math-0229$
Rubinfeld, R.
running time, see time complexity
Russo, D.
Ruzzo, W.
$bindex-math-0230$
$bindex-math-0231$
Safra, S.
Saks, M.
SAT, see SATISFIABILITY
SAT $bindex-math-0232$
$bindex-math-0233$
(SAT, r-UNSAT)
SAT-UNSAT
SATISFIABILITY (SAT)
1. paddability
2. self-reducibility
Savitch, W.
Savitch's Theorem
SBHP, see SPACE BOUNDED HALTING PROBLEM
SC, see SET COVER
Schaefer, T. J.
Schöning, U.
Schwartz, J.
scorpion graph
SCS, see SHORTEST COMMON SUPERSTRING
search problems
second moment method
Seiferas, J. I.
self-correction procedure
self-reducibility
1. c-
2. d-
3. T-
4. tt-
self-reducing tree
Selman, A.
SET COVER (SC)
SET SPLITTING
Shallit, J.
Shamir, A.
Shannon, C. E.
Shepherdson, J. C.
Sheu, M.
Shor, P. W.
SHORTEST COMMON SUPERSTRING (SCS)
SID, see SUBSET INTERCONNECTION DESIGN
$bindex-math-0239$
$bindex-math-0240$
$bindex-math-0241$ -complete set
$bindex-math-0242$ -predicate
σ-field
SIMDAG machine
Simon, J.
simple set
simple strategy
simplex
1. face
simplicial complex
1. abstract
2. collapsible
3. contractible
4. Euler characteristic
5. geometric
6. geometric representation
simplicial mapping
simulation
Sinclair, A.
Sipser, M.
Sivakumar, D.
slice function
Smolensky, R.
SMT, see STEINER MINIMUM TREE
SMT-DG, see SMT-IN-DIGRAPH
SMT-G, see STEINER MINIMUM TREE IN GRAPH
SMT-IN-DIGRAPH (SMT-DG)
Soare, R. I.
Solovay, R.
space $bindex-math-0244$
space $bindex-math-0245$
SPACE BOUNDED HALTING PROBLEM (SBHP)
space complexity
1. of PTM
space-constructibility, fully
Space Hierarchy Theorem
spanning tree
sparse set
Spencer, J.
Spielman, D.
SQRT, see SQUARE ROOT MODULO AN INTEGER
SQUARE ROOT MODULO A PRIME
SQUARE ROOT MODULO AN INTEGER (SQRT)
SS, see SUBSET SUM
stage construction diagonalization
Stearns, R. E.
STEINER MINIMUM TREE (SMT)
STEINER MINIMUM TREE IN GRAPH (SMT-G)
Stockmeyer, L.
Storer, J.
straight-line arithmetic program
Strassen, V.
Straubing, H.
string
1. empty
2. length of a
STRING MATCHING
strong NP reducibility
strongly bi-immune set
1. sparse
strongly unpredictable pseudorandom generator
strongly unpredictable set
Sturgis, H. E.
subexponential density
SUBGRAPH ISOMORPHISM
Subramanian, A.
SUBSET INTERCONNECTION DESIGN (SID)
SUBSET SUM (SS)
Sudan, M.
Sudborough, J. H.
sunflower
1. center
2. petal
Swapping Lemma
1. second form
Switching Lemma
symmetric permutation, of a Boolean function
Szelepcsényi, R.
$bindex-math-0246$
$bindex-math-0247$
$bindex-math-0248$
tally set
Tape Compression Theorem
Tardos, E.
Tarjan, R. E.
TERE, see TOTALITY OF EXTENDED REGULAR EXPRESSIONS
terminal, 212; see also b-terminal
tetrahedron
$bindex-math-0250$
3-CNF, 53, 101; see also Boolean formula and quantified Boolean formula
3-DNF, 91; see also Boolean formula
3-CNF-SAT $bindex-math-0251$
3-CNF-TAU $bindex-math-0252$
3-DIMENSIONAL MATCHING (3DM)
3-DNF-SAT $bindex-math-0253$
3-DNF-TAU $bindex-math-0254$
3-QBF
3-SAT
3DM, see 3-DIMENSIONAL MATCHING
3SAT-3
threshold function
$bindex-math-0255$
$bindex-math-0256$
time complexity. 18–20
1. expected
2. of PTM
3. uniform
time complexity measure
1. logarithmic
2. reasonable
3. uniform, 23, 40,
time-constructibility, fully
Time Hierarchy Theorem
TM, see Turing machine
Toda, S.
topological criterion
TOTALITY OF EXTENDED REGULAR EXPRESSIONS (TERE)
TOTALITY OF REGULAR EXPRESSIONS (TRE)
transitive closure
trapdoor one-way function
TRAVELING SALESMAN PROBLEM (TSP)
1. approximation to
2. with triangle inequality
TRE, see TOTALITY OF REGULAR EXPRESSIONS tree
1. binary
2. decision, see decision tree
3. internal vertex
4. leaf
5. pruning
6. root
7. rooted
tree function
triangle
triangle inequality
Triesch, E.
$bindex-math-0257$
truth assignment
truth-table
truth-table reducibility, polynomial-time, 77, 263; see also k-truth-table reducibility
1. bounded
2. conjunctive
3. disjunctive
TSP, see TRAVELING SALESMAN PROBLEM
tt-condition
Turing, A.
Turing machine(s) (TM)
1. alternating, see alternating Turing machine
2. clocked
  1. enumeration of
3. computation
4. configuration
5. deterministic (DTM)
6. encoding of a
7. enumeration of
8. halting of
9. interactive
10. multi-tape
11. next configuration function
12. nondeterministic, see nondeterministic Turing machine
13. oracle, see oracle Turing machine
14. polynomial-time
15. program of a
16. probabilistic, see probabilistic Turing machine
17. quantum
18. space complexity, see space complexity
19. storage tape
20. time complexity, see time complexity
21. universal
Turing reducibility
1. log-space
2. polynomial-space
3. polynomial-time
4. positive, polynomial-time
5. work tape
2-APPROX-SAT
two-person game
1. configuration
2. polynomially bounded
3. winning strategy
2-SAT
two-sided errors
Tzeng, W.-G.
Ullman, J.
uniform complexity class
uniformity, log-space
universal hashing function
universal BPP machine
unrelativizable proof technique
UNSAT $bindex-math-0262$
UNSAT $bindex-math-0263$
UP; see also k-UP
$bindex-math-0265$
$bindex-math-0266$
$bindex-math-0267$
VC, see VERTEX COVER
$bindex-math-0268$
VC-b
VC-IN-CUBIC-GRAPHS (VC-CG)
VC-CG, see VC-IN-CUBIC-GRAPHS
Valiant, L.
van Emde Boas, P.
van Melkebeek, D.
Vazirani, U. V.
Vazirani, V. V.
vector space
vertex
1. adjacent
VERTEX COVER (VC)
1. paddability
vertex cover
Vitányi, P.
Vollmer, H.
Vuillemin, S.
Wagner, K.
Wang, J.
Watanabe, O.
weakly paddable set
Wechsung, G.
Wegener, I.
Wegman, M. N.
well-formed formula
Welsh, D. J. A.
Wigderson, A.
Wilson, C.
Winkler, P.
winning strategy
witness
Wolfe, D.
Wrathall, C.
wreath product
Wu, W.
Wyllie, J.
Yannakakis, M.
Yao, A.
Young, P.
$bindex-math-0270$
Zachos, S.
zero-knowledge proof system
1. perfect
Zero-One Law
$bindex-math-0271$
Zhou, S.
ZPP
Zuckerman, D.
Zwick, U.