Decision problem (original) (raw)
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no. Problemes amb respostes més complexes es coneixen com a . Per exemple, es pot tenir un problema de decisió «donats dos nombres x i y, x és divisor enter de y?». Aquesta és una pregunta de resposta sí o no, i la seva resposta depèn dels valors de x i de y. Un algorisme per aquest problema de decisió hauria de contestar com, donats x i y, es pot determinar si x és divisor enter de y. Els problemes de decisió acostumen a ser menys útils intuïtivament parlant que no pas els problemes funcionals, que poden tenir qualsevol resposta, no només sí o no. Per exemple, un problema funcional pot ser "donats dos nombres x i y, quan és x dividit per y?". Tot i això, per a la teoria de complexitat computacional, és més senzill d'estudiar els problemes de decisió. A la teoria de la computabilitat, intenta classificar els problemes de decisió basant-se en com de «difícils» són, en termes de que es necessiten per l'algorisme més eficient per aquest problema de decisió. (ca) Rozhodovací problém je v informatice, speciálně v teorii složitosti a teorii vyčíslitelnosti, otázka v nějakém systému s odpovědí ANO-NE v závislosti na hodnotě vstupu.Například, problém „pro dvě čísla x a y, dělí x hodnotu y beze zbytku?“ je rozhodovací problém, kde odpověď „ANO“ nebo „NE“ závisí na vstupech. Rozhodovací problémy se typicky a přirozeně objevují v otázkách rozhodnutelnosti, kdy se ptáme, zda existuje pro určení existence nějakých matematických objektů nebo pro jejich příslušnost do nějaké množiny. Některé problémy v matematice jsou nerozhodnutelné. Rozhodovací problém je jednoduchá forma obecnějšího , který může vracet obecnější odpovědi než jednoduché ANO-NE. Záleží na přesné formulaci otázky, příbuzné problémy k výše uvedenému příkladu jsou „pro dvě čísla x a y, jaký je podíl y/x“ a „pro dané y, jaký je nejmenší netriviální dělitel y“. Druhý příklad je formulován jako optimalizační problém důležitý a používaný v praxi, který hledá nejlepší odpověď na danou otázku podle nějakého kritéria (taky nazývaného kriteriální funkce). Metoda pro řešení rozhodovacího problému, zadaná ve formě algoritmu, se nazývá rozhodovací procedura pro příslušný problém. Rozhodovací problém, který lze vyřešit algoritmem, se nazývá rozhodnutelný. Známý nerozhodnutelný problém je problém zastavení. Rozhodovací problémy se zařazují do (v teorii složitosti) nebo (v teorii rekurze), které kategorizují obtížnost vlastní tomuto problému. Výzkum v teorii vyčíslitelnosti se typicky zaměřuje na rozhodovací problémy, protože nedochází ke ztrátě obecnosti (tzv. BÚNO). (cs) Στη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, ένα πρόβλημα απόφασης είναι ένα ερώτημα σε κάποιο τυπικό σύστημα που επιδέχεται μιας ναι ή όχι απάντησης, ανάλογα με τις τιμές κάποιων παραμέτρων εισόδου. Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ερωτήματα (αποφασισιμότητας), δηλαδή ερωτήματα σχετικά με την ύπαρξη ή μη κάποιας συστηματικής μεθόδου για να προσδιοριστεί αν κάποιο αντικείμενο υπάρχει ή αν ανήκει σε κάποιο σύνολο· κάποια από τα πιο σημαντικά προβλήματα των μαθηματικών είναι (μη αποφασίσιμα). Για παράδειγμα, το ακόλουθο πρόβλημα: «δοθέντων δύο αριθμών x και y, διαιρεί τέλεια ο x τον y;» είναι ένα πρόβλημα απόφασης. Η απάντηση μπορεί να είναι είτε «ναι» είτε «όχι», και εξαρτάται από τις τιμές των x και y. Μια μέθοδος για την επίλυση τέτοιου προβλήματος, δοσμένης με τη μορφή αλγορίθμου, αποκαλείται διαδικασία απόφασης. Μια διαδικασία απόφασης για το παραπάνω πρόβλημα θα έδινε τα βήματα εκείνα για να διαπιστώσουμε αν ο x διαιρεί τέλεια τον y, δοσμένων των x και y. Ένας τέτοιος αλγόριθμος είναι η , που διδάσκεται σε πολλά σχολεία. Αν το υπόλοιπο είναι ίσο με μηδέν, τότε η απάντηση στο πρόβλημα είναι «ναι», σε αντίθετη περίπτωση είναι «όχι». Ένα πρόβλημα απόφασης που δύναται να επιλυθεί με κάποιον αλγόριθμο, όπως στο παράδειγμα, αποκαλείται (ή αποφασίσιμο). Ο τομέας της υπολογιστικής πολυπλοκότητας κατηγοριοποιεί τα αποκρίσιμα προβλήματα απόφασης με κριτήριο τη δυσκολία επίλυσής τους. Υπό αυτή την έννοια, το «δύσκολο» ορίζεται βάσει των υπολογιστικών πόρων που απαιτεί ο πιο αποδοτικός αλγόριθμος για ένα συγκεκριμένο πρόβλημα. Παράλληλα, ο τομέας της θεωρίας υπολογισιμότητας κατηγοριοποιεί τα μη αποκρίσιμα προβλήματα απόφασης με το , ο οποίος αποτελεί ένα μέτρο της μη υπολογισιμότητας που είναι εγγενής σε οποιαδήποτε λύση. Μια στενά συνδεδεμένη κατηγορία των προβλημάτων απόφασης αποτελούν τα , τα οποία απαιτούν μια πιο περίπλοκη λύση από ένα απλό «ναι» ή «όχι». Ένα αντίστοιχο παράδειγμα προβλήματος είναι το εξής: «δοθέντων δύο αριθμών x και y, ποιο είναι το αποτέλεσμα του x διαιρούμενου με το y;». Τα προβλήματα απόφασης συνδέονται επίσης με τα , τα οποία απαιτούν τη βέλτιστη λύση για ένα συγκεκριμένο πρόβλημα. Υπάρχουν πρότυπες τεχνικές για το μετασχηματισμό προβλημάτων συνάρτησης σε βελτιστοποίησης, και το αντίστροφο, οι οποίες δεν αλλάζουν ιδιαίτερα την υπολογιστική δυσκολία των προβλημάτων. Για το λόγο αυτό, η έρευνα στη θεωρία υπολογισιμότητας και πολυπλοκότητας έχει επικεντρωθεί κυρίως στα προβλήματα απόφασης. (el) En kaj de , decidoproblemo estas demando en iu kun jes-aŭ-ne respondo, depende de la valoroj de kelkaj enigaj parametroj. Decidoproblemoj tipe prezentiĝas en matematikaj demandoj de , t.e., la demando pri la ekzisto de determini la ekziston de iu objekto aŭ ĝian membrecon en aro; kelkaj el la plej gravaj problemoj en matematiko estas . Ekzemple, la problemo “donite du numeroj x kaj y, ĉu x divizoras y?” estas decidoproblemo. La respondo povas esti aŭ ‘jes’ aŭ ‘ne,’ kaj dependas sur la valoroj de x kaj y. Solvadmetodo por decidoproblemo, donita en algoritma formo, nomiĝas decidoprocedo por tiu problemo. Decidoprocedo por la decidoproblemo “donite du numeroj x kaj y, ĉu x divizoras y?” donas la manipuloj kiuj determinas ĉu x divizoras y, donite x kaj y. Unu tia algoritmo estas , kiu ĉiuj lernantoj devas lerni. Se la cetero estas nulo, la respondo estas 'jes'; alie, ĝi estas 'ne'. Decidoproblemo kiu solveblas per algoritmo, kiel ĉi tiu ekzemplo, nomiĝas decidebla. La fako de komputa kompliko kategoriigas decideblajn decidoproblemojn laŭ kiel malfacile ili solvendas. "Malfacila", en tiu senco, priskribiĝas laŭ la komputaj rimedoj, kiuj la plej efika algoritmo bezonas por iu problemo. La fako de , dume, kategoriigas nedecideblajn decidoproblemojn laŭ , kiu estas mezuro de la nekomputeblo de ajna solvo. Decidoproblemoj proksime rilatas al , kiuj povas havi respondojn pli kompleksajn ol simpla "jes" aŭ "ne". Ekvivalenta funkcioproblemo estas "donite du numeroj x kaj y, kio estas x dividita per y?" Ili ankaŭ rilatas al , kiuj temas pri trovado de la plej bona respondo al specifa problemo. Ekzistas normaj teknikoj transformi funkcioproblemojn kaj problemojn de optimumigo en decidoproblemojn, kaj inverse, kiuj ne signife ŝanĝi la komputan malfacilaĵon de ĉi tiuj problemoj. Por tiu kialo, esploro en teorio de komputeblo kaj komplikteorio tipe centras sur decidoproblemojn. (eo) In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called decidable. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable. The field of computational complexity categorizes decidable decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of recursion theory, meanwhile, categorizes undecidable decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution. (en) En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son «sí» o «no». Un problema de decisión también se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, también llamado lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. La pregunta anterior sobre los números primos se puede véase también como el lenguaje de todas las frases en el alfabeto {0, 1,..., 9} tales que el entero correspondiente es primo. (es) En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat. (fr) Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri. Si parla di problemi decisionali soprattutto all'interno del campo della matematica applicata e, più nello specifico, della ricerca operativa. La versione in Inglese di questa voce definisce un problema decisionale come un problema, appartenente alla teoria della computabilità ed alla teoria della complessità computazionale, che può essere posto sotto forma di una domanda riguardante i dati in ingresso a cui possa essere data una risposta nella forma "si" oppure "no". Un esempio di problema decisionale è, dato un numero naturale, stabilire se si tratta di un numero primo. (it) 決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合、あるいはの部分集合からへの写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。 (ja) 계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다. 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한한 부분집합이기 때문에, 모든 문제는 결정 문제로 환원될 수 있다. 판정 문제를 푸는 데 쓰인 방법을 알고리즘이라고 한다. 어떤 판정 문제를 푸는 알고리즘이 있으면 그 문제는 결정 가능하다고 한다. 없으면 결정 불가능하다고 한다. (ko) In de berekenbaarheids- en complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat, afhankelijk van de gegeven invoer, met 'ja' of 'nee' beantwoord dient te worden. Het probleem "is het getal een priemgetal?" is bijvoorbeeld een beslissingsprobleem. Een beslissingsprobleem wordt beslisbaar genoemd als er een algoritme bestaat dat het voor elke invoer oplost. (nl) Inom datavetenskapen, och särskilt komplexitetsteori är ett beslutsproblem ett som ska besvaras med ja eller nej. Ett exempel på ett beslutsproblem är: kan man rita den här figuren utan att lyfta pennan? Detta problem kallas i matematiken för att hitta en Eulerstig. Märk att själva lösningen i ett beslutsproblem, i exemplet hur man ritar figuren, inte är intressant. Avsikten är att förenkla och formalisera beräkningsproblem så att man kan resonera om dem på ett matematiskt sätt. Har man väl en algoritm som löser ett beslutsproblem brukar det inte vara svårt att anpassa den till att plocka fram lösningen. (sv) Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe są tylko odpowiedzi tak i nie. Przykładowo problem „Dla danych liczb x i y, czy x jest dzielnikiem y?” jest problemem decyzyjnym. Odpowiedzią może być tak lub nie w zależności od wartości x i y. Analogicznie do problemów decyzyjnych definiuje się – na które wymagane są bardziej złożone odpowiedzi oraz problemy optymalizacyjne – polegające na znalezieniu najlepszej odpowiedzi. Teoria złożoności obliczeniowej kategoryzuje problemy decyzyjne w zależności od tego jak trudno je rozwiązać, w terminach zasobów wymaganych przez najefektywniejsze algorytmy. Natomiast teoria rekursji definiuje również hierarchię dla problemów, których nie można algorytmicznie rozwiązać, określając stopień ich „nierozwiązywalności” jako . Teoria obliczeń zwykle skupia się na problemach decyzyjnych, ponieważ są najprostsze w analizie. Odpowiednie twierdzenia przenoszą się również na problemy funkcyjne, dzięki opisanej niżej redukcji. (pl) Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão. Ou ainda: "Dado um número inteiro x, x é um número primo?". A resposta para esses problemas pode ser 'sim' ou 'não', e depende dos valores que as variáveis assumem em cada instância do problema. Para a seguinte instância do segundo problema "7 é um número primo?" a resposta é sim, já para a instância "8 é um número primo?" a resposta é não. Um problema de decisão também pode ser formalizado como o problema de verificar se uma determinada cadeia de caracteres pertence ou não a um conjunto de cadeias de caracteres, também chamado de linguagem formal. O conjunto contém exatamente as cadeias para as quais a resposta à pergunta é 'sim'. Voltando ao exemplo dos números primos proposto anteriormente, pode-se vê-lo também como a linguagem de todas as cadeias no alfabeto {0, 1, 2,..., 9} tal que o inteiro correspondente à cadeia é um número primo. Problemas de decisão estão intimamente ligados com , que podem ter respostas mais complexas do que um simples 'sim' ou 'não'. Um típico problema de função é "dado dois números x e y, para qual x temos que y é divisível por x?". Esses tipos de problema estão relacionados também com os problemas de otimização, os quais se preocupam em achar a melhor solução para um problema particular. Métodos usados para resolver problemas de decisão são chamados de procedimentos ou algoritmos. Um algoritmo para o problema anterior explicaria em quais situações y é divisível por x, dados x e y. Um problema de decisão que pode ser resolvido por algum algoritmo é chamado de problema de decisão decidível. O campo de complexidade computacional classifica problemas de decisão decidíveis pelo grau de dificuldade em resolvê-los. "Dificuldade", nesse sentido, é descrito em termos de esforço computacional necessário para o algoritmo mais eficiente para um determinado problema. O campo da teoria da recursão, entretanto, classifica problemas através do grau de insolubilidade da Teoria da Computação e da Complexidade Computacional (no inglês, Turing degree), a qual é uma medida da não-computabilidade inerente a cada solução. Pesquisas na área da teoria da computabilidade têm focado principalmente nos problemas de decisão. (pt) Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров. Например, проблема «даны два числа: и ; делится ли на ?» является проблемой разрешимости. Ответ может быть дан либо «да», либо «нет» и зависит от значений и . Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы из примера выше должна определять совокупность действий, которые следует предпринять для проверки делимости нацело на для данных чисел. Один из таких алгоритмов — деление столбиком — изучается в начальной школе. Остаток, равный нулю, означает ответ «да», в противном случае — «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой. Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы ответом к задаче было бы «да» или «нет». Исследования в области теории рекурсии часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи. (ru) У теорії обчислюваності і теорії складності обчислень, проблема вибору або задача про ухвалення рішень — це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Рішення проблеми зазвичай з'являються в математичних питаннях алгоритмічного розв'язання, тобто в питаннях про існування ефективного методу для визначення наявності будь-якого об'єкта або його належність множині. Деякі з важливих математичних проблем нерозв'язні. Наприклад, питання «задані два числа x і y, чи ділиться x на y без залишку?» — буде проблемою вибору. Відповідь може бути або 'так' або 'ні', і залежить від значень x і y. Метод розв'язання проблеми вибору описаний у формі алгоритму називається алгоритмом вибору, алгоритмом ухвалення рішень або розв'язувальною процедурою для цієї проблеми. Розв'язувальна процедура для проблеми вибору «задані два числа x і y, чи x ділиться на y без залишку?» має надати покроковий набір дій для визначення чи ділиться x на y без залишку для даних x і y. Одним з таких алгоритмів є ділення в стовпчик. Якщо залишок від ділення буде нулем, то тоді відповідь 'так', інакше 'ні'. Проблема вибору, яка може бути розв'язана за допомогою алгоритму, такого як в цьому прикладі, зветься розв'язною. Теорія складності обчислень розрізняє розв'язні проблеми вибору за складністю їхнього розв'язання. «Складний», у цьому значені, описаний в термінах потрібних найефективнішому алгоритму розв'язання певної проблеми. Теорія обчислюваності, тим часом, розрізняє нерозв'язні проблеми вибору за степенем Тюрінга, який є мірою нерозв'язності властивою будь-якому розв'язку. Проблема вибору тісно пов'язана з функціональною проблемою, яка передбачає більш складні відповіді ніж так чи ні. Дослідження в теорії обчислень зазвичай сфокусовані на проблемах вибору, бо від цього не втрачається загальність, тому, що кожна функціональна проблема може бути перетворена у проблему вибору. (uk) 在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（英語：Decision problem）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式（decision procedure）。對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」決策程式將確定 x 是否整除 y。一種這樣的演算法是長除法，如果餘數為 0，則原決定性問題的答案為「是」，否則為「否」。若某決定性問題可以被一些演算法所解決，則稱此問題可決定（decidable）。 決定性問題與功能性問題（Function problem，或）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除 x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 計算複雜度的領域中，分類可決定問題的依據在於「此問題有多難被解決」。在此標準下，所謂的「難」是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在中，並沒有失去其普遍性。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Decision_Problem.svg?width=300 |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=Vo3fBwAAQBAJ&q=%22decision+problem%22 https://www.google.com/books/edition/Decision_Procedures/SaUywbXY9C8C%3Fhl=en&pg=PR1 https://www.google.com/books/edition/Recursively_Enumerable_Sets_and_Degrees/9I7Pl00LU5gC%3Fhl=en&pg=PP1 https://www.google.com/books/edition/The_Calculus_of_Computation/0MbX7xVpffAC%3Fhl=en&pg=PR2 |
| dbo:wikiPageID | 8336 (xsd:integer) |
| dbo:wikiPageLength | 9862 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1108111861 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Prime dbr:NP_(complexity) dbr:Algorithm dbr:Decidability_(logic) dbr:Infinite_set dbr:Computability_theory dbr:NP-complete dbr:Alphabet_(computer_science) dbr:Long_division dbr:Complement_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:Computational_resource dbr:Function_problem dbr:Partial_function dbr:String_(computer_science) dbr:Many-one_reduction dbr:Gödel_numbering dbr:Linear_programming dbr:Polynomial-time_reduction dbr:Formal_language dbr:Halting_problem dbr:Counting_problem_(complexity) dbr:ALL_(complexity) dbc:Computational_problems dbc:Computability_theory dbr:Co-NP-complete dbr:Effective_method dbr:Boolean_satisfiability_problem dbr:Polynomial_time dbr:Indicator_function dbr:Operations_research dbr:Recursive_set dbr:Recursively_enumerable_set dbr:Search_problem dbr:Word_problem_(mathematics) dbr:Undecidable_problem dbr:List_of_undecidable_problems dbr:Yes–no_question dbr:Turing_degree dbr:Traveling_salesman_problem dbr:Recursion_theory dbr:Complete_problem dbr:Logical_theory dbr:Primality_testing dbr:File:Decision_Problem.svg |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Authority_control dbt:Cite_book dbt:Main dbt:Reflist dbt:Short_description dbt:Mathematical_logic |
| dcterms:subject | dbc:Computational_problems dbc:Computability_theory |
| gold:hypernym | dbr:Question |
| rdf:type | owl:Thing dbo:Work yago:WikicatComputationalProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| rdfs:comment | En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat. (fr) 決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合、あるいはの部分集合からへの写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。 (ja) 계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다. 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한한 부분집합이기 때문에, 모든 문제는 결정 문제로 환원될 수 있다. 판정 문제를 푸는 데 쓰인 방법을 알고리즘이라고 한다. 어떤 판정 문제를 푸는 알고리즘이 있으면 그 문제는 결정 가능하다고 한다. 없으면 결정 불가능하다고 한다. (ko) In de berekenbaarheids- en complexiteitstheorie is een beslissingsprobleem een computationeel probleem dat, afhankelijk van de gegeven invoer, met 'ja' of 'nee' beantwoord dient te worden. Het probleem "is het getal een priemgetal?" is bijvoorbeeld een beslissingsprobleem. Een beslissingsprobleem wordt beslisbaar genoemd als er een algoritme bestaat dat het voor elke invoer oplost. (nl) Inom datavetenskapen, och särskilt komplexitetsteori är ett beslutsproblem ett som ska besvaras med ja eller nej. Ett exempel på ett beslutsproblem är: kan man rita den här figuren utan att lyfta pennan? Detta problem kallas i matematiken för att hitta en Eulerstig. Märk att själva lösningen i ett beslutsproblem, i exemplet hur man ritar figuren, inte är intressant. Avsikten är att förenkla och formalisera beräkningsproblem så att man kan resonera om dem på ett matematiskt sätt. Har man väl en algoritm som löser ett beslutsproblem brukar det inte vara svårt att anpassa den till att plocka fram lösningen. (sv) En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no. Problemes amb respostes més complexes es coneixen com a . Per exemple, es pot tenir un problema de decisió «donats dos nombres x i y, x és divisor enter de y?». Aquesta és una pregunta de resposta sí o no, i la seva resposta depèn dels valors de x i de y. Un algorisme per aquest problema de decisió hauria de contestar com, donats x i y, es pot determinar si x és divisor enter de y. (ca) Rozhodovací problém je v informatice, speciálně v teorii složitosti a teorii vyčíslitelnosti, otázka v nějakém systému s odpovědí ANO-NE v závislosti na hodnotě vstupu.Například, problém „pro dvě čísla x a y, dělí x hodnotu y beze zbytku?“ je rozhodovací problém, kde odpověď „ANO“ nebo „NE“ závisí na vstupech. Rozhodovací problémy se typicky a přirozeně objevují v otázkách rozhodnutelnosti, kdy se ptáme, zda existuje pro určení existence nějakých matematických objektů nebo pro jejich příslušnost do nějaké množiny. Některé problémy v matematice jsou nerozhodnutelné. (cs) Στη θεωρία υπολογισιμότητας και τη θεωρία πολυπλοκότητας, ένα πρόβλημα απόφασης είναι ένα ερώτημα σε κάποιο τυπικό σύστημα που επιδέχεται μιας ναι ή όχι απάντησης, ανάλογα με τις τιμές κάποιων παραμέτρων εισόδου. Τα προβλήματα απόφασης εμφανίζονται συνήθως σε μαθηματικά ερωτήματα (αποφασισιμότητας), δηλαδή ερωτήματα σχετικά με την ύπαρξη ή μη κάποιας συστηματικής μεθόδου για να προσδιοριστεί αν κάποιο αντικείμενο υπάρχει ή αν ανήκει σε κάποιο σύνολο· κάποια από τα πιο σημαντικά προβλήματα των μαθηματικών είναι (μη αποφασίσιμα). (el) En kaj de , decidoproblemo estas demando en iu kun jes-aŭ-ne respondo, depende de la valoroj de kelkaj enigaj parametroj. Decidoproblemoj tipe prezentiĝas en matematikaj demandoj de , t.e., la demando pri la ekzisto de determini la ekziston de iu objekto aŭ ĝian membrecon en aro; kelkaj el la plej gravaj problemoj en matematiko estas . (eo) In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y. One such algorithm is long division. If the remainder is zero the answer is 'yes', (en) En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son «sí» o «no». (es) Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri. Si parla di problemi decisionali soprattutto all'interno del campo della matematica applicata e, più nello specifico, della ricerca operativa. (it) Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe są tylko odpowiedzi tak i nie. Przykładowo problem „Dla danych liczb x i y, czy x jest dzielnikiem y?” jest problemem decyzyjnym. Odpowiedzią może być tak lub nie w zależności od wartości x i y. Analogicznie do problemów decyzyjnych definiuje się – na które wymagane są bardziej złożone odpowiedzi oraz problemy optymalizacyjne – polegające na znalezieniu najlepszej odpowiedzi. (pl) Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão. Ou ainda: "Dado um número inteiro x, x é um número primo?". A resposta para esses problemas pode ser 'sim' ou 'não', e depende dos valores que as variáveis assumem em cada instância do problema. Para a seguinte instância do segundo problema "7 é um número primo?" a resposta é sim, já para a instância "8 é um número primo?" a resposta é não. (pt) Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров. Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление произведения двух чисел, поиск наиболее быстрого алгоритма умножения чисел и оптимизационные задачи, в частности задача коммивояжёра в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы ответом к задаче было бы «да» или «нет». (ru) У теорії обчислюваності і теорії складності обчислень, проблема вибору або задача про ухвалення рішень — це запитання в деякій формальній системі з відповіддю так або ні, залежно від значення деяких вхідних параметрів. Рішення проблеми зазвичай з'являються в математичних питаннях алгоритмічного розв'язання, тобто в питаннях про існування ефективного методу для визначення наявності будь-якого об'єкта або його належність множині. Деякі з важливих математичних проблем нерозв'язні. (uk) 在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（英語：Decision problem）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式（decision procedure）。對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」決策程式將確定 x 是否整除 y。一種這樣的演算法是長除法，如果餘數為 0，則原決定性問題的答案為「是」，否則為「否」。若某決定性問題可以被一些演算法所解決，則稱此問題可決定（decidable）。 決定性問題與功能性問題（Function problem，或）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除 x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 計算複雜度的領域中，分類可決定問題的依據在於「此問題有多難被解決」。在此標準下，所謂的「難」是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 (zh) |
| rdfs:label | Problema de decisió (ca) Rozhodovací problém (cs) Entscheidungsproblem (de) Πρόβλημα απόφασης (el) Decidoproblemo (eo) Problema de decisión (es) Decision problem (en) Problème de décision (fr) Problema decisionale (it) 결정 문제 (ko) 決定問題 (ja) Beslissingsprobleem (nl) Problem decyzyjny (teoria obliczeń) (pl) Problema de decisão (pt) Задача разрешимости (ru) Beslutsproblem (sv) Задача вибору (uk) 決定性問題 (zh) |
| owl:sameAs | freebase:Decision problem yago-res:Decision problem wikidata:Decision problem http://bn.dbpedia.org/resource/সিদ্ধান্ত_সমস্যা dbpedia-ca:Decision problem dbpedia-cs:Decision problem dbpedia-de:Decision problem dbpedia-el:Decision problem dbpedia-eo:Decision problem dbpedia-es:Decision problem dbpedia-fa:Decision problem dbpedia-fr:Decision problem dbpedia-he:Decision problem dbpedia-hr:Decision problem http://hy.dbpedia.org/resource/Լուծելիության_պրոբլեմ dbpedia-it:Decision problem dbpedia-ja:Decision problem http://kn.dbpedia.org/resource/ನಿರ್ಣಯ_ಪ್ರಶ್ನೆ dbpedia-ko:Decision problem dbpedia-nl:Decision problem dbpedia-pl:Decision problem dbpedia-pt:Decision problem dbpedia-ru:Decision problem dbpedia-sh:Decision problem dbpedia-simple:Decision problem dbpedia-sr:Decision problem dbpedia-sv:Decision problem dbpedia-th:Decision problem dbpedia-uk:Decision problem dbpedia-zh:Decision problem https://global.dbpedia.org/id/2zsUe |
| prov:wasDerivedFrom | wikipedia-en:Decision_problem?oldid=1108111861&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Decision_Problem.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Decision_problem |
| is dbo:wikiPageRedirects of | dbr:Word_problem_(computability) dbr:Solvable_problem dbr:Decidability_problems dbr:Decidable_problem dbr:Decision_problems dbr:Decision_procedure dbr:Decision_variant dbr:Decision_version |
| is dbo:wikiPageWikiLink of | dbr:Proof_of_impossibility dbr:Robert_Shostak dbr:Saul_Kripke dbr:Enumeration_algorithm dbr:List_of_computability_and_complexity_topics dbr:Monadic_predicate_calculus dbr:Monte_Carlo_algorithm dbr:Mortality_(computability_theory) dbr:NE_(complexity) dbr:NP_(complexity) dbr:MAX-3SAT dbr:Metamathematics dbr:Parity_P dbr:Principles_of_Mathematical_Logic dbr:Decider_(Turing_machine) dbr:Approximation-preserving_reduction dbr:History_of_computing_hardware dbr:Betweenness dbr:DSPACE dbr:DTIME dbr:Ulrike_Sattler dbr:Vertex_cover dbr:Decidability_(logic) dbr:Depth-first_search dbr:ESPACE dbr:EXPSPACE dbr:Independence_(mathematical_logic) dbr:Induced_subgraph_isomorphism_problem dbr:Integer_factorization dbr:Interior_algebra dbr:Intersection_non-emptiness_problem dbr:Intuitionistic_type_theory dbr:L-reduction dbr:Levi's_lemma dbr:List_of_knapsack_problems dbr:List_of_mathematical_logic_topics dbr:PSPACE-complete dbr:Simon's_problem dbr:Space_hierarchy_theorem dbr:Weighted_automaton dbr:Weighted_majority_algorithm_(machine_learning) dbr:♯P dbr:Complete_coloring dbr:Computability dbr:Mathematical_logic dbr:Maximum_cut dbr:Generic-case_complexity dbr:Omega_language dbr:Oracle_machine dbr:NP-easy dbr:Structural_rule dbr:Schaefer's_dichotomy_theorem dbr:Chromatic_polynomial dbr:Clique_problem dbr:Co-NP dbr:Genetic_algorithm dbr:Glossary_of_artificial_intelligence dbr:Graph_homomorphism dbr:Graph_minor dbr:Greatest_common_divisor dbr:Bottleneck_traveling_salesman_problem dbr:Model_checking dbr:NC_(complexity) dbr:NL_(complexity) dbr:Conjugacy_problem dbr:Constraint_satisfaction_problem dbr:Context-sensitive_grammar dbr:Cook–Levin_theorem dbr:Equivalence_problem dbr:LOGCFL dbr:L_(complexity) dbr:Ordinal_priority_approach dbr:Logic_of_graphs dbr:MAXEkSAT dbr:Steiner_tree_problem dbr:Clique_cover dbr:Closest_string dbr:Combinatorial_optimization dbr:Complement_(complexity) dbr:Complexity_class dbr:Component_(graph_theory) dbr:Computable_number dbr:Computation_tree dbr:Computational_complexity_theory dbr:Computational_problem dbr:Computer_bridge dbr:Emptiness_problem dbr:Feedback_vertex_set dbr:Function_problem dbr:Hamiltonian_completion dbr:Hamiltonian_path_problem dbr:Decidability dbr:Kernelization dbr:Kripke_semantics dbr:PCP_theorem dbr:P_(complexity) dbr:Padding_argument dbr:Penrose_tiling dbr:Petri_net dbr:Post_correspondence_problem dbr:Probabilistically_checkable_proof dbr:Quantum_supremacy dbr:Static_program_analysis dbr:TC_(complexity) dbr:Tag_system dbr:Many-one_reduction dbr:Maximum_common_induced_subgraph dbr:Maximum_satisfiability_problem dbr:P/poly dbr:BPP_(complexity) dbr:Business_decision_mapping dbr:Time_complexity dbr:Travelling_salesman_problem dbr:Turing's_proof dbr:Type_system dbr:Type_theory dbr:Wilhelm_Ackermann dbr:Domatic_number dbr:Galactic_algorithm dbr:Hedonic_game dbr:Julia_Robinson dbr:Las_Vegas_algorithm dbr:Polynomial-time_reduction dbr:Minimum-cost_flow_problem dbr:P-complete dbr:TFNP dbr:Promise_problem dbr:Resource_bounded_measure dbr:Unrestricted_grammar dbr:Alan_Turing dbr:3-dimensional_matching dbr:EXPTIME dbr:E_(complexity) dbr:Ambiguity dbr:Ambiguous_grammar dbr:Exact_cover dbr:Fallibilism dbr:First-order_logic dbr:PP_(complexity) dbr:PSPACE dbr:Parametric_search dbr:Digi-Comp_II dbr:Digraph_realization_problem dbr:Formal_language dbr:Graph_realization_problem dbr:Graph_theory dbr:Graph_toughness dbr:History_of_group_theory dbr:Unary_numeral_system dbr:List_of_NP-complete_problems dbr:List_of_PSPACE-complete_problems dbr:Quadratic_knapsack_problem dbr:RE_(complexity) dbr:R_(complexity) dbr:Reduction_(complexity) dbr:Regular_language dbr:2-EXPTIME dbr:Gödel's_incompleteness_theorems dbr:Halting_problem dbr:Hans_Hermes dbr:Courcelle's_theorem dbr:Solovay–Strassen_primality_test dbr:Art_gallery_problem dbr:ALL_(complexity) dbr:AWPP_(complexity) dbr:Advice_(complexity) dbr:Lambda_calculus dbr:Bin_packing_problem dbr:Bipartite_dimension dbr:Bipartite_realization_problem dbr:Co-NP-complete dbr:Effective_method dbr:Hierarchy_(mathematics) dbr:Word_problem_(computability) dbr:Word_problem_for_groups dbr:Recursive_language dbr:System_F dbr:Uninterpreted_function dbr:Dieter_Rödding dbr:Differentiable_manifold dbr:Dominating_set dbr:Arthur–Merlin_protocol dbr:Boolean_algebra dbr:Boolean_circuit dbr:Boolean_satisfiability_problem dbr:CC_(complexity) dbr:Polynomial_hierarchy dbr:Square-free_integer dbr:St-connectivity dbr:Circuit_satisfiability_problem dbr:Group_isomorphism_problem dbr:Guillotine_cutting dbr:Ian_Horrocks dbr:Minimum_spanning_tree dbr:Optimization_problem dbr:Randomized_algorithm dbr:Raphael_M._Robinson dbr:Search_problem dbr:Word_problem_(mathematics) dbr:Knapsack_problem dbr:Longest_path_problem dbr:Mastermind_(board_game) dbr:Satisfiability dbr:Satisfiability_modulo_theories dbr:Set_cover_problem dbr:Subset_sum_problem dbr:Semantics dbr:Skolem_arithmetic dbr:Solvable_problem dbr:UP_(complexity) dbr:Undecidable_problem dbr:Unit_testing dbr:Viable_system_model dbr:Wang_tile dbr:Expression_(mathematics) dbr:Expressive_power_(computer_science) dbr:FL_(complexity) dbr:FNP_(complexity) dbr:FP_(complexity) dbr:Immerman–Szelepcsényi_theorem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Turing_jump dbr:Tracing_garbage_collection dbr:Planted_clique dbr:Type_inhabitation dbr:Exact_quantum_polynomial_time dbr:Existential_theory_of_the_reals dbr:Finitely_generated_group dbr:Subgraph_isomorphism_problem dbr:NEXPTIME dbr:NP-completeness dbr:NP-equivalent dbr:NP-hardness dbr:NSPACE dbr:NTIME dbr:Richardson's_theorem dbr:NL-complete dbr:Monochromatic_triangle dbr:Multiway_number_partitioning dbr:Yes–no_question dbr:PolyL dbr:Polynomial-time_counting_reduction dbr:Time_hierarchy_theorem dbr:Turing_reduction dbr:Nonelementary_problem dbr:Residue-class-wise_affine_group dbr:Set_packing dbr:Outline_of_logic dbr:P_versus_NP_problem dbr:Property_testing dbr:Rice's_theorem dbr:Size-change_termination_principle dbr:Set_splitting_problem dbr:Turing_degree dbr:Structural_complexity_theory dbr:Decidability_problems dbr:Decidable_problem dbr:Decision_problems dbr:Decision_procedure dbr:Decision_variant dbr:Decision_version |
| is foaf:primaryTopic of | wikipedia-en:Decision_problem |
