Definition:Reducible

Disambiguation

This page lists articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article.

Reducible may refer to:

Reducible Fraction

Let $q = \dfrac a b$ be a vulgar fraction.

Then $q$ is defined as being reducible if and only if $q$ is not in canonical form.

That is, if and only if there exists $r \in \Z: r \ne 1$ such that $r$ is a divisor of both $a$ and $b$.

Such a fraction can therefore be reduced by dividing both $a$ and $b$ by $r$.

Reducible Polynomial

Let $K$ be a field.

A reducible polynomial over $K$ is a nonconstant polynomial over $K$ that can be expressed as the product of two polynomials over $K$ of smaller degree.

Reducible Linear Representation

Let $\rho: G \to \GL V$ be a linear representation.

$\rho$ is reducible if and only if there exists a non-trivial proper vector subspace $W$ of $V$ such that:

$\forall g \in G: \map {\map \rho g} W \subseteq W$

That is, such that $W$ is invariant for every linear operator in the set $\set {\map \rho g: g \in G}$.

Reducible $G$-Module

Let $M$ be a $G$-module.

Then $M$ is reducible if and only if the corresponding linear representation is reducible.

Mapping Reducible, also known as Many-One Reducible

Let $\Sigma, \Sigma'$ be finite sets.

Let:

\(\ds L\)

\(\subseteq\)

\(\ds \Sigma^*\)

\(\ds L'\)

\(\subseteq\)

\(\ds \Sigma'^*\)

be sets of finite strings over $\Sigma$ and $\Sigma'$ respectively, where:

$\Sigma^*$ denotes the set of all finite strings over the alphabet $\Sigma$.

Let $f : \Sigma^* \to \Sigma'^*$ be a computable function such that, for all $w \in \Sigma^*$:

$w \in L \iff \map f w \in L'$

Then, $f$ is a mapping reduction from $L$ to $L'$.