M-complete

the time needed for N plus the time needed for the reduction;

the maximum of the space needed for N and the space needed for the reduction.

Many-one reductions are a special case and a weaker form of Turing Reduction s where only one invocation of the oracle is allowed, and only at the end. Turing reductions are sometimes more convenient for designing reduction algorithms, but their power also causes several important classes such as NP to not be closed under Turing reductions.

Many-one reductions are often subjected to additional resource restrictions, for example that the function is computable in polynomial time or logarithmic space; see Polynomial-time Reduction and Log-space Reduction for details.

Many-one reductions were first used by Emil Post in 1944. Later Norman Shapiro used the same concept in 1956 under the name ''strong reducibility''.

DEFINITIONS

Formal languages

→ Γ^--- that has the property that

If such a function ''f'' exists, we say that "''A'' is many-one reducible to ''B''".

Subsets of natural numbers

Given two sets

A,B \subseteq \mathbb{N}

we say

A

is many-one reducible or '''m-reducible''' to

B

and write
:

A \leq_m B

if there exists a Total Computable Function

f

with
:

A = f^{-1}

{Link without Title} .
If additionally

f

is Injective we say

A

is 1-reducible to

B

and write
:

A \leq_1 B.

If
:

A \leq_m B \, \mathrm{and} \, B \leq_m A

we say

A

is many-one equivalent or '''m-equivalent''' to

B

and write
:

A \equiv_m B.

If
:

A \leq_1 B \, \mathrm{and} \, B \leq_1 A

we say

A

is 1-equivalent to

B

and write
:

A \equiv_1 B.

REMARKS

We say that a class C of languages (or a subset of the Power Set of the natural numbers) is ''closed under many-one reducibility'' if there exists no reduction from a language in C to a language outside C. If a class is closed under many-one reducibility, then many-one reduction can be used to show that a problem is in C by reducing a problem in C to it. Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including P , NP , L , NL , Co-NP , PSPACE , EXP , and many others.

PROPERTIES

the Relation many-one reducibility and 1 reducibility are Transitive and Reflexive and thus induce a Partial Order on the Powerset of the natural numbers.

if $A \le B$ then $\mathbb{N} \setminus A \le \mathbb{N} \setminus B$

REFERENCES

E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin Of The American Mathematical Society 50 (1944) 284-316

Norman Shapiro, "Degrees of Computability", Transactions Of The American Mathematical Society 82, (1956) 281-299

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT MANY-ONE REDUCTION

	recursion theory

	computational complexity theory

Information About

M-complete