| dbo:abstract
|
- En teoria de la computabilitat i teoria de la complexitat computacional, una reducció és una transformació d'un en un altre problema. Depenent de la transformació utilitzada aquesta pot ser utilitzada per a definir en un conjunt de problemes. Intuïtivament, si un problema A és reduïble a un problema B, una solució per a B dona una solució per a A. D'aquesta forma, la resolució d'A no pot ser més difícil que la resolució de B. Escrivim A ≤ B, habitualment amb una subescriptura al ≤ per a indicar el tipus de reducció que es fa servir. (ca)
- Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird. Gibt es einen Algorithmus für das zweite Problem, so lässt sich über die Reduktion auch das erste lösen. Die Reduzierbarkeit ist daher eine Relation auf der Menge der Probleme, durch welche die Berechenbarkeit oder die Komplexität zweier Probleme zueinander in Bezug gesetzt werden kann. Der Grundgedanke, Reduktionen für die Untersuchung von Problemen zu verwenden, geht auf einen Aufsatz des Mathematikers Emil Post aus dem Jahr 1944 zurück. Es werden verschiedene Arten von Reduktionen unterschieden. Die häufigsten sind dabei die One-one- oder Many-one-Reduktion, sowie die Truth-table- und Turing-Reduktion (letztere nach Alan Turing benannt). Jede von ihnen enthält jeweils die vorangegangenen als Sonderfall. Während in der Berechenbarkeitstheorie meist der Nachweis des Vorhandenseins einer bestimmten Reduktion zwischen zwei Problemen genügt, werden in der Komplexitätstheorie zusätzliche Anforderungen an den Ressourcenverbrauch der Reduktion gestellt. Gewöhnliche Ressourcen sind hierbei Zeit oder Speicherplatz. Dies führt auf die Begriffe der Karp- (nach Richard M. Karp) und Cook-Reduktion (nach Stephen Cook). (de)
- En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada, la reducción se puede utilizar para definir clases de complejidad en un conjunto de problemas. Intuitivamente, un problema es reducible a un problema si las soluciones de existen y dan una solución para siempre que tenga solución.Así, resolver no puede ser más difícil que resolver .Normalmente, esto se expresa de la forma , y se añade un subíndice en para indicar el tipo de reducción utilizada.Por ejemplo, se usa la letra como subíndice para indicar que la reducción puede realizarse en tiempo polinomial: . (es)
- In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first. Intuitively, problem A is reducible to problem B, if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, solving A cannot be harder than solving B. "Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, expensive need for extra hardware processor cores for a parallel solution compared to a single-threaded solution, etc.). The existence of a reduction from A to B, can be written in the shorthand notation A ≤m B, usually with a subscript on the ≤ to indicate the type of reduction being used (m : mapping reduction, p : polynomial reduction). The mathematical structure generated on a set of problems by the reductions of a particular type generally forms a preorder, whose equivalence classes may be used to define degrees of unsolvability and complexity classes. (en)
- En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B. Il y a deux utilisations des réductions.
* Montrer qu'un problème est intrinsèquement difficile. Par exemple, on utilise une réduction pour montrer que des problèmes sont indécidables : on montre alors que le problème est tellement algorithmiquement difficile, qu'il n'y a pas d'algorithmique qui le décide. Les réductions polynomiales sont utilisées pour démontrer que des problèmes sont NP-difficiles. Plus généralement, on démontre avec des réductions qu'un problème est parmi les plus difficiles d'une classe de complexité.
* Montrer qu'un problème est facile à résoudre algorithmiquement. Par exemple, si A ≤ B avec ≤ une réduction en temps polynomial, et que B appartenant à P, alors A est aussi dans P. (fr)
- 還元（かんげん、Reduction）とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着、変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。 直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。 (ja)
- 복잡도 이론과 계산 복잡도 이론에서 환산(reduction 리덕션[*])은 어떤 문제를 다른 문제로 변형하는 과정이다. transformation 트랜스포메이션[*]이라고도 한다. 문제 A가 어떤 과정을 통해 문제 B로 환산된다면 B의 해답을 가지고 A의 해답을 알 수 있기 때문에, A를 푸는 작업이 B를 푸는 작업보다 어려울 수 없다. 이를 A ≤ B라 쓰고, 흔히 ≤의 아랫첨자에 어떤 종류의 환산인지 명시해 주곤 한다. 특정한 환산은 복잡도 종류를 정의하는 데 쓰일 수 있다. 예를 들어, 곱셈 문제를 제곱 문제로 환산하는 경우를 살펴 보자. 만약 덧셈, 뺄셈, 제곱 연산, 2로 나누는 연산만 쓸 수 있다면, 두 숫자의 곱을 다음과 같이 구할 수 있다. 거꾸로 같은 두 수를 곱해서 제곱 연산을 할 수 있으므로 반대 환산도 가능하다. 이런 종류의 환산은 이라 한다. 하지만 환산 과정에 제곱 연산을 단 한 번, 그리고 맨 마지막에 사용할 수 있다는 제약을 가하면 환산은 어려워진다. 이러한 제약이 있다면 어떠한 일반적인 환산 과정이 존재하지 않는데, 같은 무리수를 유리수로부터 계산해야 할 수 있기 때문이다. 하지만 반대로 제곱 연산은 곱셈 한 번을 맨 마지막에 사용하기만 해도 되고, 따라서 일반적으로 '곱셈은 제곱 연산보다 더 어렵다'는 결과를 얻어낼 수 있다. 이런 종류의 환산은 이라 한다. (ko)
- Redukcja – termin teorii złożoności obejmujący różnorodne metody przekształcania danego problemu w inny, w pewien sposób co najwyżej tak samo trudny, w celu klasyfikacji problemów ze względu na pewną ich cechę: rozpoznawalność, rozstrzygalność, czy przynależność do jednej z wielu klas złożoności. Poszczególne redukcje, często ze sobą powiązane, noszą nazwiska badaczy teorii złożoności, m.in. redukcja Turinga, , , . (pl)
- En reduktion är inom datalogi en metod som transformerar om ett problem till ett annat. Med reduktion kan man visa egenskaper hos problem, t.ex. visa undre gränser på hur ineffektiva lösningar på problemen måste vara. En viktig användning av reduktioner utgörs av bevis av att ett problem är . För att visa detta löses ett redan känt NP-fullständigt problem med hjälp av det problem som ska visas vara NP-svårt. Denna datavetenskapsrelaterade artikel saknar väsentlig information. Du kan hjälpa till genom att lägga till den. (sv)
- Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro. Dependendo da transformação utilizada, isto pode ser usado para definir classes de complexidade em um conjunto de problemas.Intuitivamente, o problema A é redutível ao problema B se existe uma maneira de transformar uma solução para B numa solução para A sempre que A tem solução. Assim, solucionar A não pode ser mais difícil que solucionar B. Escrevemos A ≤mB, geralmente com um símbolo subscrito no ≤ para indicar o tipo de redução que foi usada (m: redução por mapeamento; P: redução polinomial). (pt)
- Зведення в теорії складності обчислень — перетворення однієї задачі до іншої. У загальному випадку, для алгоритму, що перетворює примірники задачі на примірники задачі , які мають ту саму відповідь («так» або «ні»), кажуть, що зводиться до , таким чином, звідність — це відношення між двома задачами. За допомогою такого зв'язку можна доводити обчислюваність задачі або її належність до того чи іншого класу складності. Деякі види зведень: , , , . Зведення за Тюрінгом — найзагальніша форма зведення: деякий алгоритм (обчисле́нний на машині Тюрінга) можна викликати будь-яку кількість разів, при цьому кожен виклик буде вважатися одним кроком алгоритму; для формального визначення звідності за Тюрінгом використовується поняття тюрінг-машини з оракулом. (uk)
- Сведе́ние в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи в экземпляры задачи , которые имеют тот же ответ («да» или «нет»), говорят, что сводится к , таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или её принадлежность тому или иному классу сложности. Некоторые виды сведений: сведение по Куку, сведение по Карпу, , . Сведение по Тьюрингу — наиболее общая форма сведения: некоторый алгоритм (вычислимый на машине Тьюринга) может быть вызван любое количество раз, при этом каждый вызов будет считаться за один шаг алгоритма; для формального определения сводимости по Тьюрингу используется понятие тьюринг-машины с оракулом. (ru)
- 在可計算性理論與計算複雜性理論中，所謂的歸約是將某個轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。 一般寫作A ≤m B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。 將一組問題歸約到特定類型所產生的數學結構，通常形成预序关系，其等價類可用於定義求解難度和複雜度。 (zh)
|
| rdfs:comment
|
- En teoria de la computabilitat i teoria de la complexitat computacional, una reducció és una transformació d'un en un altre problema. Depenent de la transformació utilitzada aquesta pot ser utilitzada per a definir en un conjunt de problemes. Intuïtivament, si un problema A és reduïble a un problema B, una solució per a B dona una solució per a A. D'aquesta forma, la resolució d'A no pot ser més difícil que la resolució de B. Escrivim A ≤ B, habitualment amb una subescriptura al ≤ per a indicar el tipus de reducció que es fa servir. (ca)
- 還元（かんげん、Reduction）とは、計算可能性理論や計算複雑性理論において、ある問題を別の問題に変換することを意味する。帰着、変換などとも呼ばれる。変換の仕方によっては、問題の複雑性クラスを定義するのに使われる。 直観的に、問題 A が問題 B に還元されるとき、B の解法によって A の答えも得られる。従って A を解くことは B を解くよりも困難ではない。これを A ≤ B のように表記し、≤ に添え字をつけて還元の種類を示す。 (ja)
- Redukcja – termin teorii złożoności obejmujący różnorodne metody przekształcania danego problemu w inny, w pewien sposób co najwyżej tak samo trudny, w celu klasyfikacji problemów ze względu na pewną ich cechę: rozpoznawalność, rozstrzygalność, czy przynależność do jednej z wielu klas złożoności. Poszczególne redukcje, często ze sobą powiązane, noszą nazwiska badaczy teorii złożoności, m.in. redukcja Turinga, , , . (pl)
- En reduktion är inom datalogi en metod som transformerar om ett problem till ett annat. Med reduktion kan man visa egenskaper hos problem, t.ex. visa undre gränser på hur ineffektiva lösningar på problemen måste vara. En viktig användning av reduktioner utgörs av bevis av att ett problem är . För att visa detta löses ett redan känt NP-fullständigt problem med hjälp av det problem som ska visas vara NP-svårt. Denna datavetenskapsrelaterade artikel saknar väsentlig information. Du kan hjälpa till genom att lägga till den. (sv)
- Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro. Dependendo da transformação utilizada, isto pode ser usado para definir classes de complexidade em um conjunto de problemas.Intuitivamente, o problema A é redutível ao problema B se existe uma maneira de transformar uma solução para B numa solução para A sempre que A tem solução. Assim, solucionar A não pode ser mais difícil que solucionar B. Escrevemos A ≤mB, geralmente com um símbolo subscrito no ≤ para indicar o tipo de redução que foi usada (m: redução por mapeamento; P: redução polinomial). (pt)
- 在可計算性理論與計算複雜性理論中，所謂的歸約是將某個轉換為另一個問題的過程。可用歸約法定義某些問題的複雜度類（因轉換過程而異）。 以直覺觀之，如果存在能有效解決問題B的算法，也可以作為解決問題A的子程序，則將問題A稱為「可歸約」到問題B，因此求解A並不會比求解B更困難。 一般寫作A ≤m B，通常也在≤符號下標使用的歸約類型（m：映射縮小，p：多項式縮減）。 將一組問題歸約到特定類型所產生的數學結構，通常形成预序关系，其等價類可用於定義求解難度和複雜度。 (zh)
- Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird. Gibt es einen Algorithmus für das zweite Problem, so lässt sich über die Reduktion auch das erste lösen. Die Reduzierbarkeit ist daher eine Relation auf der Menge der Probleme, durch welche die Berechenbarkeit oder die Komplexität zweier Probleme zueinander in Bezug gesetzt werden kann. Der Grundgedanke, Reduktionen für die Untersuchung von Problemen zu verwenden, geht auf einen Aufsatz des Mathematikers Emil Post aus dem Jahr 1944 zurück. (de)
- En calculabilité et en théorie de la complexité, une réduction est un algorithme transformant une instance d'un problème algorithmique en une ou plusieurs instances d'un autre problème. S'il existe une telle réduction d'un problème A à un problème B, on dit que le problème A se réduit au problème B. Dans ce cas, le problème B est plus difficile que le problème A, puisque l'on peut résoudre le problème A en appliquant la réduction puis un algorithme pour le problème B. On écrit alors A ≤ B. Il y a deux utilisations des réductions. (fr)
- En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada, la reducción se puede utilizar para definir clases de complejidad en un conjunto de problemas. (es)
- In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A sufficiently efficient reduction from one problem to another may be used to show that the second problem is at least as difficult as the first. The mathematical structure generated on a set of problems by the reductions of a particular type generally forms a preorder, whose equivalence classes may be used to define degrees of unsolvability and complexity classes. (en)
- 복잡도 이론과 계산 복잡도 이론에서 환산(reduction 리덕션[*])은 어떤 문제를 다른 문제로 변형하는 과정이다. transformation 트랜스포메이션[*]이라고도 한다. 문제 A가 어떤 과정을 통해 문제 B로 환산된다면 B의 해답을 가지고 A의 해답을 알 수 있기 때문에, A를 푸는 작업이 B를 푸는 작업보다 어려울 수 없다. 이를 A ≤ B라 쓰고, 흔히 ≤의 아랫첨자에 어떤 종류의 환산인지 명시해 주곤 한다. 특정한 환산은 복잡도 종류를 정의하는 데 쓰일 수 있다. 예를 들어, 곱셈 문제를 제곱 문제로 환산하는 경우를 살펴 보자. 만약 덧셈, 뺄셈, 제곱 연산, 2로 나누는 연산만 쓸 수 있다면, 두 숫자의 곱을 다음과 같이 구할 수 있다. 거꾸로 같은 두 수를 곱해서 제곱 연산을 할 수 있으므로 반대 환산도 가능하다. 이런 종류의 환산은 이라 한다. (ko)
- Сведе́ние в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи в экземпляры задачи , которые имеют тот же ответ («да» или «нет»), говорят, что сводится к , таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или её принадлежность тому или иному классу сложности. (ru)
- Зведення в теорії складності обчислень — перетворення однієї задачі до іншої. У загальному випадку, для алгоритму, що перетворює примірники задачі на примірники задачі , які мають ту саму відповідь («так» або «ні»), кажуть, що зводиться до , таким чином, звідність — це відношення між двома задачами. За допомогою такого зв'язку можна доводити обчислюваність задачі або її належність до того чи іншого класу складності. Деякі види зведень: , , , . (uk)
|
