polyomino 405

If anxn+ an–1xn–1 +…+ a1x+ a0= 0 for all values x,

then it must be the case that an= an–1 =…= a1= a0= 0.

(To see this, write anxn+ an–1xn–1 +…+ a1x+ a0=

. For a large

value of x, the term anxnwill adopt a very large value,

and the expression inside the parentheses will adopt a

value close to 1 + 0 +…+ 0 + 0 = 1. Thus the value of

the entire polynomial expression will not be zero,

unless an= 0. Repeating this argument shows that all

coefficients would then have to be zero.) As a conse-

quence we have:

If two polynomials produce the same output

values for each input value x, then the two

polynomials must be identical, that is, their

coefficients match.

(The difference of these two polynomials would be a

new polynomial that always produces the zero output.)

This second statement explains why the process of

EQUATING COEFFICIENTS

is valid.

The

FUNDAMENTAL THEOREM OF ALGEBRA

assures

us that any degree-npolynomial equation of the form

anxn+ an–1xn–1 +…+ a1x+ a0= 0 has precisely nroots

(when counted with multiplicity). Some roots may be

COMPLEX NUMBERS

. There exist arithmetic formulae

for finding the roots of any quadratic equation, any

CUBIC EQUATION

, and any

QUARTIC EQUATION

. In 1824

algebraist N

IELS

H

ENRIK

A

BEL

proved that there are no

analogous formulae for solving fifth- and higher-degree

polynomial equations.

Evaluating a degree-npolynomial typically requires

the computation of n+ (n–1) +…+ 2 + 1 + 0 =

multiplications. For instance, in the expression

2x3+ 3x2+ 4x+ 5 = 2 ×x×x×x+ 3 ×x×x+ 4 ×x+ 5

the multiplication sign “ד appears 3 + 2 + 1 + 0 = 6

times. This is the formula for the nth

TRIANGULAR

NUMBER

. The process of performing a

NESTED MULTI

-

PLICATION

reduces the number of products needed to

just n. For example, rewriting 2x3+ 3x2+ 4x+ 5 as

x(x(2x+ 3) + 4) + 5 reduces the number of multipli-

cations present from six to three. The process of

SYN

-

THETIC DIVISION

is intimately connected with nested

multiplications.

L

AGRANGE

’

S FORMULA

shows that given any n+ 1

points, drawn in the plane, each with a distinct xcoor-

dinates, there exists a polynomial function of degree n

whose graph passes through each of those points. Thus

it is always possible to “fit” a polynomial function to

any finite set of data points. This is useful for the pur-

poses of

INTERPOLATION

and

EXTRAPOLATION

.

A polynomial may have more than one variable.

For example, 5x2y+ 7xy2– y3is a degree-three bivari-

ate polynomial.

See also

BINOMIAL

;

COMPLETING THE SQUARE

;

D

ESCARTES

’

SRULEOFSIGNS

;

DIFFERENCE OF TWO

CUBES

;

DIFFERENCE OF TWO SQUARES

;

DISCRIMINANT

;

FACTOR THEOREM

;

FACTORIZATION

;

HISTORY OF EQUA

-

TIONS AND ALGEBRA

(essay);

MONOMIAL

;

REMAINDER

THEOREM

;

ROOT

;

SOLUTION BY RADICALS

; T

AYLOR

SERIES

;

TRINOMIAL

.

polynomial time A computation is said to run in

polynomial time if the number of elementary steps

required to complete the computation can be expressed

as a

POLYNOMIAL

function of the size of the input. For

example, if a basic step is to add or multiply two sin-

gle-digit numbers, then the computation of multiplying

two n-digit numbers via ordinary long multiplication

requires at most 4n2steps. (Multiplying each of the

pair of digits requires n2steps, and summing all results,

with carrying, is at most 3n2steps.) Thus long multipli-

cation runs in polynomial time.

Computations that do not run in polynomial time

are said to run in exponential time. For example, the

task of listing all possible arrangements of nobjects

grows as n

FACTORIAL

. As the factorial function will

exceed any polynomial function of nfor sufficiently

large values of n, the operation of listing all possible

orders is exponential. Even with the most powerful

computers, exponential time computations generally

require an infeasible amount of time to complete. Poly-

nomial time algorithms, however, are more practical.

See also

NP COMPLETE

;

TRAVELING

-

SALESMAN

PROBLEM

.

polyomino Generalizing the concept of a domino, a

polyomino is a shape made by adjoining 1×1 squares

along entire edge lengths in such a way that no corner

of one square lies at an interior point of another

n(n+ 1)

———–

2