Computational complexity theory (original) (raw)

dbo:abstract

La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme. Es considera que un problema és inherentment difícil si la seva solució requereix recursos importants, sigui quin sigui l'algorisme utilitzat. La teoria formalitza aquesta intuïció, introduint models matemàtics de càlcul per estudiar aquests problemes i quantificant-ne la complexitat computacional, és a dir, la quantitat de recursos necessaris per resoldre'ls, com el temps i la necessitat d'emmagatzematge. També s'utilitzen altres mesures de complexitat, com ara la quantitat de comunicació (utilitzada en complexitat de comunicació), el nombre de portes en un circuit (utilitzat en complexitat de circuits) i el nombre de processadors (utilitzat en informàtica paral·lela). Una de les funcions de la teoria de la complexitat computacional és determinar els límits pràctics del que els ordinadors poden i no poden fer. El problema P versus NP, un dels set problemes del Premi del Mil·lenni, està dedicat al camp de la complexitat computacional. Camps estretament relacionats en la informàtica teòrica són l'anàlisi d'algorismes i la teoria de la computabilitat. La primera es dedica a analitzar la quantitat de recursos que necessita un algorisme en particular per resoldre un problema, mentre que la segona fa una pregunta més general sobre tots els possibles algorismes que es podrien utilitzar per resoldre el mateix problema. Més concretament, la teoria de la complexitat computacional intenta classificar problemes que es poden o no resoldre amb recursos restringits adequadament. Al seu torn, imposar restriccions als recursos disponibles és el que distingeix la complexitat computacional de la teoria de la computabilitat: aquesta darrera teoria es pregunta quin tipus de problemes es poden, en principi, resoldre algorítmicament. (ca)
نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية (مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي). وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية، والفرق بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة، بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، أما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية أي أن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها بواسطة خوارزمية. (ar)
Teorie složitosti je odvětvím v informatice a matematice, které se zaměřuje na klasifikaci dle jejich vlastní složitosti a určení vztahů mezi nimi. Ke studiu a určení složitosti těchto problémů definuje výpočetní modely, jako je Turingův stroj nebo RAM, na kterých je simuluje a určuje složitost (typicky časovou a paměťovou). Používají se i další míry složitosti, jako množství komunikace (v ), počet hradel obvodu (ve ), počet přístupů do keše (v analýze kešování) a počet procesorů (v paralelním programování). Jeden z cílů teorie složitosti je určit praktické limity toho, co počítače dokážou spočítat a co ne. V tomto kontextu je výpočetní problém chápán jako úkol, který lze vyřešit na počítači, čímž se myslí mechanickou aplikací postupných kroků pomocí algoritmu. Konkrétní zadání problému je tzv. instance a algoritmus vrátí řešení instance. Příkladem je situace, kdy chceme zjistit, zdali je nějaké přirozené číslo n prvočíslem nebo ne. Jedná se o rozhodovací problém, kde instancí problému jsou přirozená čísla a výsledkem je odpověď ANO/NE. Problém, například výše zmíněné testování prvočíselnosti, se považuje za těžký, pokud jeho řešení potřebuje značné zdroje bez ohledu na to, jaký algoritmus je použit. Příbuzné oblasti informatiky jsou analýza algoritmů a teorie vyčíslitelnosti. Hlavním rozdílem mezi analýzou algoritmů a teorií složitosti je, že analýza algoritmů se zabývá množstvím potřebných zdrojů, které potřebuje konkrétní algoritmus, zatímco teorie složitosti zjišťuje obecnější otázky týkající se všech algoritmů, které se dají použít pro řešení určitého problému. Snaží se tedy klasifikovat problémy podle daných omezení na dostupné zdroje. Tedy zavedení omezení na dostupné zdroje odlišuje teorii složitosti od teorie vyčíslitelnosti, které se ptá, jaké problémy lze, v principu, vyřešit algoritmicky. (cs)
Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο χρόνος, οπότε μιλάμε για τη χρονική πολυπλοκότητα του αλγορίθμου, δηλαδή πόσα «βήματα» χρειάζεται να εκτελέσει ο αλγόριθμος συναρτήσει της του, και ο χώρος, οπότε μιλάμε για τη χωρική πολυπλοκότητα, δηλαδή πόσο χώρο (μνήμη) χρειάζεται ο αλγόριθμος συναρτήσει της εισόδου του. Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι παράλληλοι επεξεργαστές χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα. (el)
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen. Die Komplexität eines Problems ist wiederum die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst. Die Komplexitätstheorie unterscheidet sich von der Berechenbarkeitstheorie, die sich mit der Frage beschäftigt, welche Probleme prinzipiell algorithmisch gelöst werden können. Demgegenüber besteht das wichtigste Forschungsziel der Komplexitätstheorie darin, die Menge aller lösbaren Probleme zu klassifizieren. Insbesondere versucht man, die Menge der effizient lösbaren Probleme, deren Ressourcenverbrauch in der Praxis bewältigt werden kann, von der Menge der inhärent schwierigen Probleme abzugrenzen. (de)
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e., the amount of resources needed to solve them, such as time and storage. Other measures of complexity are also used, such as the amount of communication (used in communication complexity), the number of gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do. The P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity. Closely related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kinds of problems can, in principle, be solved algorithmically. (en)
La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad. Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de computación matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria. Una de las metas de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema. La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica. (es)
Konplexutasun konputazionalaren teoria edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena. Arazo bat berez zaila gisa sailkatzen da, bere konponbideak baliabide konputazional kopuru handia eskatzen badu, erabilitako algoritmoa edozein dela ere. Konplexutasun konputazionalaren teoriak baieztapen hori formalizatzen du arazo horiek aztertzeko eta haiek ebazteko behar diren baliabideen kopuruaren kuantifikaziorako eredu konputazional matematikoak sartuz, hala nola denbora eta memoria. Konplexutasun konputazionalaren teoriaren helburuetako bat ordenagailuan egin daitekeenaren eta egin ezin denaren muga praktikoak zehaztea da. Konplexutasun konputazionalaren teoriarekin lotutako beste alor batzuk algoritmoen analisia eta konputagarritasunaren teoria dira. Algoritmoen analisiaren eta konplexutasun konputazionalaren teoriaren arteko alde nabarmena da lehena algoritmo jakin batek arazo bat ebazteko behar duen baliabide kopurua zehazteaz arduratzen da, eta, bigarrena, berriz, arazo bera ebazteko erabil litezkeen algoritmo posible guztiak aztertzen ditu. Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki. (eu)
La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée …) requis par un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité. (fr)
La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema. Una distinzione informale, ma di grande rilievo, è quella posta tra i cosiddetti problemi facili, di cui si conoscono algoritmi di risoluzione efficienti, e difficili, di cui gli unici algoritmi noti non sono efficienti. Ad esempio la maggior parte della crittografia moderna si fonda sull'esistenza di problemi ritenuti difficili; ha enorme rilevanza lo studio di tali problemi, poiché, qualora si dimostrasse l'esistenza di un algoritmo efficiente per un problema ritenuto difficile, i sistemi crittografici basati su di esso non sarebbero più sicuri. (it)
계산 복잡도 이론(計算複雜度理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. (ko)
計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 (ja)
Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Een computationeel probleem is een probleem dat door een computer kan worden opgelost. Een voorbeeld van een probleem dat computationeel is, is de vraag of een getal wel of niet priem is. Dit kan worden bepaald door middel van een priemgetaltest. Een probleem wordt gezien als inherent moeilijk, als het voor alle denkbare algoritmes veel tijd of geheugen in beslag neemt. Computationele complexiteitstheorie beschrijft dus de praktische limieten van computers. (nl)
Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. Следует не путать теорию сложности вычислений с теорией вычислимости, которая занимается поиском ответа на вопрос о том, какие задачи могут быть вообще решены с помощью алгоритмов. Основная задача исследований в теории сложности вычислений заключается в классификации всех разрешимых задач. В частности, делаются попытки разделить множество задач с эффективными алгоритмами решения от множества трудно разрешимых задач. (ru)
Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. Слід не плутати теорію складності обчислень з теорією обчислюваності, яка займається пошуком відповіді на запитання про те, які задачі можуть бути взагалі розв'язані за допомогою алгоритмів. Основна задача досліджень в теорії складності обчислень полягає у класифікації всіх розв'язних задач. Зокрема, робляться спроби відокремити множину задач з ефективними алгоритмами розв'язання від множини важко розв'язних задач. (uk)
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。 (zh)

dbo:wikiPageExternalLink

dbo:wikiPageWikiLink

dbp:wikiPageUsesTemplate

rdfs:comment

La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée …) requis par un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité. (fr)
계산 복잡도 이론(計算複雜度理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. (ko)
計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 (ja)
Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven. Een computationeel probleem is een probleem dat door een computer kan worden opgelost. Een voorbeeld van een probleem dat computationeel is, is de vraag of een getal wel of niet priem is. Dit kan worden bepaald door middel van een priemgetaltest. Een probleem wordt gezien als inherent moeilijk, als het voor alle denkbare algoritmes veel tijd of geheugen in beslag neemt. Computationele complexiteitstheorie beschrijft dus de praktische limieten van computers. (nl)
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。 (zh)
نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. (ar)
La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si. Un problema computacional és una tasca resolta per un ordinador. Un problema de càlcul es pot resoldre mitjançant l'aplicació mecànica de passos matemàtics, com ara un algorisme. (ca)
Teorie složitosti je odvětvím v informatice a matematice, které se zaměřuje na klasifikaci dle jejich vlastní složitosti a určení vztahů mezi nimi. Ke studiu a určení složitosti těchto problémů definuje výpočetní modely, jako je Turingův stroj nebo RAM, na kterých je simuluje a určuje složitost (typicky časovou a paměťovou). Používají se i další míry složitosti, jako množství komunikace (v ), počet hradel obvodu (ve ), počet přístupů do keše (v analýze kešování) a počet procesorů (v paralelním programování). Jeden z cílů teorie složitosti je určit praktické limity toho, co počítače dokážou spočítat a co ne. (cs)
Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. (el)
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen. Die Komplexität eines Problems ist wiederum die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst. (de)
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. (en)
La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad. (es)
Konplexutasun konputazionalaren teoria edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena. Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki. (eu)
La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema. Con complessità di un algoritmo o efficienza di un algoritmo ci si riferisce dunque alle risorse di calcolo richieste. I problemi sono classificati in differenti classi di complessità, in base all'efficienza del migliore algoritmo noto in grado di risolvere quello specifico problema. (it)
Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. (uk)
Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. (ru)

is dbo:wikiPageRedirects of