Интуитивно задача А сводима к задаче B, если алгоритм решения задачи B (если он существует) также можно использовать в качестве подпрограммы для эффективного решения задачи A. Когда это верно, решение A не может быть сложнее, чем решение задачи B. Более высокая сложность означает более высокую оценку требуемых вычислительных ресурсов в данном контексте. Например, большие затраты по времени, большая потребность в памяти, дорогостоящая потребность в дополнительных ядрах аппаратного процессора.
Математическая структура, сгенерированная на множестве задач редукциями определенного типа, обычно формирует предзаказ, классы эквивалентности которого могут быть использованы для определения степеней неразрешимости и классов сложности.
Математическое определение
В математике редукция – это переписывание процесса в более простую форму. Например, процесс переписывания дробной части в один с наименьшим знаменателем целого числа (при сохранении числителя целочисленным) называется «редукцией доли». Переписывание радикального (или «коренного») примера с наименьшим возможным целым числом и радикалом называется «редукцией радикала». Сюда же относятся и различные формы редукции чисел.
Типы математической редукции
Как описано в приведенном выше примере, существуют два основных типа редукций, используемых в сложных вычислениях, многократных сокращениях и сокращениях Тьюринга. Многократное сокращение отображает экземпляры одной проблемы на случай появления другой. Сокращения Тьюринга позволяют вычислить решение одной проблемы, предполагая, что другая проблема тоже будет легко решена. Многократная редукция – более сильный тип сокращения Тьюринга и более эффективно разделяет проблемы на отдельные классы сложности. Однако увеличение ограничений на многократное сокращение затрудняет их поиск, и тут на помощь часто приходит количественная редукция.
Классы сложности
Задача завершена для одного класса сложности, если каждая проблема в классе сводится к этой задаче, и она также находится в нем. Любое решение задачи может в сочетании с сокращениями использоваться для решения каждой проблемы в классе.
Проблема редукции
Однако сокращения должны быть легкими. Например, вполне возможно свести сложную задачу, такую как проблема логической выполнимости, к вполне тривиальной. Например, определить, равно ли число нулю, за счет того, что редукционная машина решает проблему в экспоненциальном времени и выводит ноль, только если есть решение. Однако этого мало, потому что, хотя мы можем решить новую проблему, выполнение сокращения так же сложно, как и решение старой проблемы. Аналогичным образом, сокращение, вычисляющее неисчислимую функцию, может уменьшить неразрешимую проблему до уровня разрешимой. Как отмечает Майкл Сипсер во «Введении в теорию вычислений»: «Редукция должна быть простой, по сравнению со сложностью типичных задач в классе. Если сама редукция была трудноисчислимой, то она не обязательно даст легкое решение проблем, связанных с задачей».
Задачи оптимизации
В случае задач на оптимизацию (максимизации или минимизации) математики сводятся к тому, что редукция это то, что помогает отображать максимально простые решения. Этот прием регулярно используется для решения подобных задач различной степени сложности.
Редукция гласных
В фонетике этим словом называют любое изменение акустического качества гласных, связанное с изменениями напряжения, звучности, продолжительности, громкости, артикуляции или положения в слове, и которое на слух воспринимается как «ослабление». Редукция – это то, что делает гласные короче.
Такие гласные часто называются редуцированными или слабыми. Напротив, нередуцированные гласные могут быть описаны как полные или сильные.
Редукция в языке
Фонетическая редукция чаще всего связана с централизацией гласных, т. е. уменьшением количества движений языка при их произнесении, как с характерным изменением многих безударных гласных на концах английских слов на что-то приближающееся к schwa. Хорошо изученным примером редукции гласных является нейтрализация акустических различий в безударных гласных, что происходит во многих языках. Наиболее распространенным примером этого явления считается звук schwa.
Общие черты
Продолжительность звука является общим фактором в редукции: при быстрой речи, гласные уменьшаются из-за физических ограничений артикуляторных органов, например, язык не может двигаться в прототипическое положение быстро или полностью, чтобы получить полноценный гласный звук (сравните с отсечением). Различные языки имеют разные типы редукции гласных, и это одна из трудностей в овладении языком. Изучение гласных второго языка – это целая наука.
Сокращение гласных, связанное с напряжением, является основным фактором развития индоевропейского аблаута, а также других изменений, восстановленных исторической лингвистикой.
Языки без редукции
В некоторых языках, таких как финский, хинди и классический испанский, как утверждается, не хватает редукции гласных. Их часто называют слоговыми языками. На другом конце спектра мексиканский испанский язык характеризуется сокращением или потерей безударных гласных, главным образом, когда они находятся в контакте со звуком "s".
Редукция с точки зрения биологии и биохимии
Редукцией иногда называют коррекцию перелома, вывиха или грыжи. Также редукция в биологии – это акт уменьшения какого-либо органа в результате эволюционных или физиологических процессов. Любой процесс, при котором электроны добавляются к атому или иону (как путем удаления кислорода или добавления водорода) и сопровождающийся окислением, называется редукцией. Не стоит забывать и про редукцию хромосом.
Редукция в философии
Сокращение (редукционизм) охватывает несколько связанных философских тем. Можно выделить по крайней мере три типа: онтологическую, методологическую и эпистемическую. Несмотря на то что аргументы за и против редукционизма часто включают в себя сочетание позиций, связанных со всеми тремя типами редукций, эти различия являются значительными, потому что между различными типами нет единства.
Онтология
Онтологическая редукция – это идея о том, что каждая конкретная биологическая система (например, организм) состоит только из молекул и их взаимодействий. В метафизике эту идею часто называют физикализмом (или материализмом), и она предполагает в биологическом контексте, что биологические свойства контролируют физические свойства и каждый конкретный биологический процесс (или токен) метафизически идентичен какому-то конкретному физико-химическому процессу. Этот последний принцип иногда называют уменьшением токена, в отличие от более сильного принципа, согласно которому каждый тип биологического процесса идентичен типу физико-химического процесса.
Онтологическая редукция в этом более слабом смысле сегодня является мейнстримной позицией среди философов и биологов, хотя философские детали остаются спорными (например, существуют ли действительно возникающие свойства?). Различные концепции физикализма могут давать различные последствия для онтологической редукции в биологии. Отрицание физикализма витализмом – мнение о том, что биологические системы управляются силами не физико-химическими, в значительной степени представляют исторический интерес. (Витализм также допускает различные концепции, особенно в отношении того, как понимаются не физико-химические силы) Некоторые авторы энергично заявляли о значимости метафизических понятий в дискуссиях по редукционизму в биологии.
Методология
Методологическая редукция – это идея о том, что биологические системы наиболее эффективно изучаются на самом низком возможном уровне, и что экспериментальные исследования должны быть направлены на выявление молекулярных и биохимических причин всего сущего. Общим примером такого типа стратегии является разложение сложной системы на части: биолог может исследовать клеточные части организма, чтобы понять его поведение, или исследовать биохимические компоненты клетки, чтобы понять ее особенности. Хотя методологический редукционизм часто мотивируется презумпцией онтологического сокращения, эта процедурная рекомендация не вытекает непосредственно из нее. На самом деле, в отличие от редукции токенов, методологический редукционизм может быть довольно противоречивым. Утверждается, что исключительно редукционистские стратегии исследований демонстрируют систематические предвзятости, которые упускают из виду соответствующие биологические особенности и что для некоторых вопросов более плодотворная методология заключается в интеграции открытия молекулярных причин с исследованием функций более высокого уровня.
Эпистема
Эпистическое сокращение – это идея о том, что знание об одной научной области (обычно о процессах более высокого уровня) может быть сведено к другому корпусу научных знаний (обычно относительно более низкого или более фундаментального уровня). Хотя одобрение некоторой формы эпистемического сокращения может быть мотивировано онтологическим снижением в сочетании с методологическим редукционизмом (например, прошлым успехом редукционистских исследований в биологии), возможность эпистемического сокращения не вытекает непосредственно из их взаимосвязи. Действительно, дебаты о редукции в философии, биологии (и философии науки вообще), были сосредоточены на этом третьем типе сокращения как наиболее спорном из всех. Прежде чем оценивать любую редукцию одного совокупного знания к другому, следует изучить концепцию этих органов знаний и то, что это будет означать для их «сокращения». Предложен ряд различных моделей редукции. Таким образом, дискуссия о редукции биологии не только вращалась вокруг того, насколько возможна эпистемическая редукция, но также и тех ее понятий, которые играют роль в реальных научных исследованиях и дискуссиях. Можно выделить две основные категории:
- модели редукции теории, которые утверждают, что одна теория может быть логически выведена из другой теории;
- модели пояснительной редукции, которые фокусируются на том, могут ли функции более высокого уровня объясняться более низкими характеристиками.
Общий вывод
Определения редукции из разных наук, упомянутые в этой статье – это далеко не предел, ведь на самом деле их гораздо больше. Несмотря на все различия в определении редукции, у всех них есть нечто общее. Прежде всего, редукция воспринимается как сокращение, уменьшение, упрощение и сведения чего-то более сложного, громоздкого и системного, к чему-то более простому, понятному и легко объяснимому. Это ключевая идея, объясняющая популярность термина "редукция" в столь многих, не связанных друг с другом, науках. Качественная редукция кочует из науки в науку, делая каждую из них более простой и понятной как профессиональным ученым, так и простым обывателям.
