| dbo:abstract
|
- In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'. (en)
- Nella teoria della complessità computazionale, un problema di funzione è un problema computazionale dove ci si aspetta una singola uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quello di un problema di decisione, cioè, non è solo "SÌ" o "NO". Esempi notevoli includono il problema del commesso viaggiatore, che richiede la strada presa dal commesso viaggiatore, e il problema della fattorizzazione degli interi, che richiede la lista dei fattori. I problemi di funzione sono più complicati da studiare dei problemi di decisione perché non hanno un analogo ovvio in termini di linguaggi, e perché la nozione di riduzione tra problemi è più sottile in quanto si deve trasformare l'uscita così come l'entrata. I problemi di funzione possono essere ordinati in classi di complessità allo stesso modo dei problemi di decisione. Ad esempio è l'insieme dei problemi di funzione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale, ed è l'insieme dei problemi di funzione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale. Per tutti i problemi di funzione per i quali la soluzione è polinomialmente limitata, c'è un problema decisionale analogo tale che il problema di funzione può essere risolto mediante a quel problema decisionale. Per esempio, il problema decisionale analogo al problema del commesso viaggiatore è questo: Dato un grafo diretto ponderato e un intero K, c'è un cammino hamiltoniano (o ciclo hamiltoniano se il commesso deve ritornare a casa) con un peso totale minore di o uguale a K? Data una soluzione a questo problema, possiamo risolvere il problema del commesso viaggiatore come segue. Sia il numero degli spigoli e sia il peso dello spigolo . Per prima cosa riproporzioniamo e perturbiamo i pesi degli spigoli assegnando allo spigolo il nuovo peso . Questo non cambia il cammino hamiltoniano più breve, ma assicura che esso sia unico. Ora si aggiungano i pesi di tutti gli spigoli per ottenere un peso totale . Si trovi il peso del più breve cammino hamiltoniano mediante ricerca binaria: c'è un cammino hamiltoniano con peso ; c'è un cammino con peso ecc. Poi, avendo trovato il peso del più breve cammino hamiltoniamo, si determini quali spigoli sono nel cammino chiedendo per ciascuno spigolo se c'è un cammino hamiltoniano con peso per il grafo modificato, così che lo spigolo abbia peso (se non c'è tale cammino nel grafo modificato, allora lo spigolo deve essere nel cammino più breve per il grafo originale). Questo pone il problema del commesso viaggiatore nella classe di complessità FPNP (la classe dei problemi di funzione che possono essere risolti in tempo polinomiale su una macchina di Turing deterministica con un per un problema in NP), e infatti esso è completo per quella classe. (it)
- 계산 복잡도 이론에서 함수 문제란 판정 문제가 아닌 문제들, 다시 말해서 답이 예/아니오보다 복잡한 문제들이다. 이를테면, 외판원 문제나 소인수 분해 문제는 답이 인수의 목록으로 나온다. 일반적으로 함수 문제는 판정 문제보다 다루기 힘들다. 함수 문제도 판정 문제와 같은 방식으로 복잡도 종류를 나눌 수 있다. 는 결정론적 튜링 기계가 다항 시간에 풀 수 있는 함수 문제의 집합이고, 는 비결정론적 튜링 기계가 다항 시간에 풀 수 있는 함수 문제의 집합이다. (ko)
- 関数問題（かんすうもんだい、function problem）とは、計算量理論において、各入力に対してある出力を返���形式の問題をいう。評価問題とも呼ばれる。文字列上の写像で表される。主に判定問題（関数問題のうち出力がであるようなもの）と対比して用いられることが多い。 (ja)
- Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma ) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO. Notáveis exemplos incluem o problema do caixeiro viajante, que indaga qual rota foi feita pelo caixeiro viajante, e o , que indaga pela lista de fatores. Problemas de função são mais trabalhosos de estudar que os problemas de decisão porque eles não tem nenhuma analogia óbvia em termos de linguagem, e porque a noção de redução entre problemas é mais sutil do que você ter transformar a saída, bem como a entrada. Problemas de função podem ser colocados dentro de problemas de classe de complexidade, assim como nos problemas de decisão. Por exemplo é da linha de funções de problemas que podem ser resolvidos pela Máquina de Turing em , e é da linha de funções que podem ser resolvidas por uma Máquina de Turing não determinística em . Por todas os problemas de função em que a solução é polinomialmente limitada, há em um análogo problema de decisão que o problema de função pode ser resolvido por uma redução em tempo polinomial para aquele problema de decisão. Por exemplo, o problema de decisão análogo ao do caixeiro viajante é: Dado um grafo direcionado ponderado e um inteiro K, existe um (ou se o caixeiro viajante necessita voltar pra casa) o peso total inferior ou igual a K? Dada uma solução para esse problema, nós podemos resolver o problema do caixeiro viajante como é mostrado a seguir. Deixe ser o número de arestas e ser o peso da aresta . Primeiro, redimensione e mexa os pesos das arestas, atribuindo a aresta the new weight . Isso não muda o menor caminho Hamiltoniano, mas tenha certeza de que ele é único. Agora, adicione os pesos de todas as arestas para ter um peso total . Encontre o peso do menor caminho Hamiltoniano por busca binária: existe um caminho Hamiltonian com peso ; existe um caminho com peso etc. Então, tendo encontrado os pesos do menor caminho Hamilton, determine quais arestas estão no caminho perguntando para cada aresta se existe um caminho Hamiltoniano com peso para o grafo modificado de modo que a aresta tenha peso (se não existe tal caminho no gráfico modificado, então a aresta deve estar no menor caminho para o grafo original). Isso coloca o problema do caixeiro viajante na classe de complexidade FPNP (a classe de problemas de funções que podem ser solucionadas em tempo polinomial em uma Máquina de Turing Determinística com uma Máquina Oráculo para um problema em NP), e de fato ele é completo para aquela classe. (pt)
- функціональною проблемою у теорії складності обчислень є обчислювальна складність, де для кожного введеного значення очікується окреме вихідне значення (обчислюваної функції), але воно більш складне, ніж у проблемі вибору. Для функціональних проблем вихідне значення зазвичай не просто «так» або «ні». (uk)
- 在計算複雜性理論內，功能性問題或者函式問題（英語：Function problem）是一種，對任何一種輸入都預期會有單一個輸出，但是輸出不像是決定性問題一樣這麼單純。換句話說，輸出不只YES跟NO。重要的範例像是旅行推銷員問題，詢問一張圖是否有可以繞過每一點的不重複路徑（輸出為路徑），以及整數分解，輸出為輸入的質因數。 因為沒有明顯類比的語言，功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，功能性問題歸約的過程也比較微妙。功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說是指可以用確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的P），而是指可以用非確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的NP）。 對所有能在多項式時間內解決的的功能性問題，一定存在一個雷同的決定型問題，可以用多項式時間圖靈歸約將後者歸約為前者的方式，解決這個功能性問題。舉例，旅行推銷員問題的決定型問題版本如下： 給定一個有權重的有向圖和一個整數K，是否存在一個哈密頓路徑（或者哈密頓回路，如果問題指定推銷員在經過所有城市後一定要回到家）並且走過的路徑權重相加小於或者等於K？ 給定這個決定性問題的解答，我們則可以解決旅行推銷員問題如下： 令為邊的數量，則是邊的權重。首先我們重新設定邊的權重，給予每個邊新的權重。這並不會改變最短路徑本身，但是會保證這路徑是唯一的。然後，將所有的邊權重加起來，得到這個圖的總權重。接著，我們使用折半搜索算法找出這條最短路徑的權重：是否有權重輕於的路徑？；是否有權重輕於的路徑？…等等。找到最短路徑的權重之後，我們藉由以下演算法確定特定某個邊是否在這個路徑上：修改的權重為之後，詢問這個圖是否還是有一個權重為的哈密頓路徑？如果修改後的圖裡面不存在這條路徑，則這個邊必定在原圖的最短路徑裡面，反之，如果修改後此路徑還是存在，則i不在原來的路徑之內。 這個演算法將旅行推銷員問題的時間複雜度放進FPNP內（可以在多項式時間之內，以決定性圖靈機和一個能解決NP問題的神諭解決的問題），並且事實上是這個複雜度類的完備問題。 (zh)
|
| rdfs:comment
|
- In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'. (en)
- 계산 복잡도 이론에서 함수 문제란 판정 문제가 아닌 문제들, 다시 말해서 답이 예/아니오보다 복잡한 문제들이다. 이를테면, 외판원 문제나 소인수 분해 문제는 답이 인수의 목록으로 나온다. 일반적으로 함수 문제는 판정 문제보다 다루기 힘들다. 함수 문제도 판정 문제와 같은 방식으로 복잡도 종류를 나눌 수 있다. 는 결정론적 튜링 기계가 다항 시간에 풀 수 있는 함수 문제의 집합이고, 는 비결정론적 튜링 기계가 다항 시간에 풀 수 있는 함수 문제의 집합이다. (ko)
- 関数問題（かんすうもんだい、function problem）とは、計算量理論において、各入力に対してある出力を返す形式の問題をいう。評価問題とも呼ばれる。文字列上の写像で表される。主に判定問題（関数問題のうち出力がであるようなもの）と対比して用いられることが多い。 (ja)
- функціональною проблемою у теорії складності обчислень є обчислювальна складність, де для кожного введеного значення очікується окреме вихідне значення (обчислюваної функції), але воно більш складне, ніж у проблемі вибору. Для функціональних проблем вихідне значення зазвичай не просто «так» або «ні». (uk)
- Nella teoria della complessità computazionale, un problema di funzione è un problema computazionale dove ci si aspetta una singola uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quello di un problema di decisione, cioè, non è solo "SÌ" o "NO". Esempi notevoli includono il problema del commesso viaggiatore, che richiede la strada presa dal commesso viaggiatore, e il problema della fattorizzazione degli interi, che richiede la lista dei fattori. (it)
- Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma ) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO. Notáveis exemplos incluem o problema do caixeiro viajante, que indaga qual rota foi feita pelo caixeiro viajante, e o , que indaga pela lista de fatores. Dado um grafo direcionado ponderado e um inteiro K, existe um (ou se o caixeiro viajante necessita voltar pra casa) o peso total inferior ou igual a K? (pt)
- 在計算複雜性理論內，功能性問題或者函式問題（英語：Function problem）是一種，對任何一種輸入都預期會有單一個輸出，但是輸出不像是決定性問題一樣這麼單純。換句話說，輸出不只YES跟NO。重要的範例像是旅行推銷員問題，詢問一張圖是否有可以繞過每一點的不重複路徑（輸出為路徑），以及整數分解，輸出為輸入的質因數。 因為沒有明顯類比的語言，功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，功能性問題歸約的過程也比較微妙。功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說是指可以用確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的P），而是指可以用非確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的NP）。 對所有能在多項式時間內解決的的功能性問題，一定存在一個雷同的決定型問題，可以用多項式時間圖靈歸約將後者歸約為前者的方式，解決這個功能性問題。舉例，旅行推銷員問題的決定型問題版本如下： 給定一個有權重的有向圖和一個整數K，是否存在一個哈密頓路徑（或者哈密頓回路，如果問題指定推銷員在經過所有城市後一定要回到家）並且走過的路徑權重相加小於或者等於K？ 給定這個決定性問題的解答，我們則可以解決旅行推銷員問題如下： (zh)
|
