*Thomas Koshy*

- Published in print:
- 2008
- Published Online:
- January 2009
- ISBN:
- 9780195334548
- eISBN:
- 9780199868766
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195334548.003.0013
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter investigates several divisibility properties of shows Catalan numbers. They include their parity and primality. Mersenne numbers are also described.

This chapter investigates several divisibility properties of shows Catalan numbers. They include their parity and primality. Mersenne numbers are also described.

*Cristopher Moore and Stephan Mertens*

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0004
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

NP refers to a class of decision problems in which yes-instances are easy to verify. That is: a decision problem is in NP if, whenever the answer for a particular instance is ‘yes’, there is a simple ...
More

NP refers to a class of decision problems in which yes-instances are easy to verify. That is: a decision problem is in NP if, whenever the answer for a particular instance is ‘yes’, there is a simple proof of this fact. Given a graph, a Hamiltonian path is a path that visits each vertex exactly once. This chapter examines the NP class of problems, first by considering the proverbial task of finding a needle in a haystack. It then looks at several definitions of NP and discusses proofs, witnesses, and lucky guesses. It shows that NP encompasses a wide range of fundamental problems, from coloring maps to untying knots and satisfying systems of constraints. It describes some of the classic problems in NP and highlights some reductions between these problems by transforming questions about graphs into questions about Boolean formulas or vice versa. The chapter also analyzes primality in NP.Less

NP refers to a class of decision problems in which yes-instances are easy to verify. That is: a decision problem is in NP if, whenever the answer for a particular instance is ‘yes’, there is a simple proof of this fact. Given a graph, a Hamiltonian path is a path that visits each vertex exactly once. This chapter examines the NP class of problems, first by considering the proverbial task of finding a needle in a haystack. It then looks at several definitions of NP and discusses proofs, witnesses, and lucky guesses. It shows that NP encompasses a wide range of fundamental problems, from coloring maps to untying knots and satisfying systems of constraints. It describes some of the classic problems in NP and highlights some reductions between these problems by transforming questions about graphs into questions about Boolean formulas or vice versa. The chapter also analyzes primality in NP.

*Cristopher Moore and Stephan Mertens*

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.003.0010
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

Certain situations require a random rather than a deterministic strategy. With a random strategy, the choices are unpredictable and the adversary may be kept off balance. This chapter focuses on the ...
More

Certain situations require a random rather than a deterministic strategy. With a random strategy, the choices are unpredictable and the adversary may be kept off balance. This chapter focuses on the variety and power of randomised algorithms. More specifically, it considers algorithms that find the smallest cut in a graph by combining random vertices until only two remain, or play games by searching the tree of possible moves in random order. It also explains how to check whether the software on a space probe is uncorrupted, how to turn a puzzle with many solutions into one with a unique solution, and how to determine whether two functions are equal. It describes tools such as random hash functions and polynomial identity testing, analyzes the nature of the primes, and looks at a series of randomised algorithms for primality based on different number-theoretic ideas. The chapter concludes by discussing several complexity classes consisting of problems that can be solved using various kinds of randomized algorithms in polynomial time.Less

Certain situations require a random rather than a deterministic strategy. With a random strategy, the choices are unpredictable and the adversary may be kept off balance. This chapter focuses on the variety and power of randomised algorithms. More specifically, it considers algorithms that find the smallest cut in a graph by combining random vertices until only two remain, or play games by searching the tree of possible moves in random order. It also explains how to check whether the software on a space probe is uncorrupted, how to turn a puzzle with many solutions into one with a unique solution, and how to determine whether two functions are equal. It describes tools such as random hash functions and polynomial identity testing, analyzes the nature of the primes, and looks at a series of randomised algorithms for primality based on different number-theoretic ideas. The chapter concludes by discussing several complexity classes consisting of problems that can be solved using various kinds of randomized algorithms in polynomial time.