This HTML5 document contains 339 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n36http://www.wisdom.weizmann.ac.il/~oded/
dbpedia-elhttp://el.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
n59http://bn.dbpedia.org/resource/
dbpedia-nohttp://no.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-bghttp://bg.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
n47https://www.springer.com/sgw/cda/frontpage/
n30https://complexityzoo.net/
dbpedia-shhttp://sh.dbpedia.org/resource/
dbpedia-hrhttp://hr.dbpedia.org/resource/
dbpedia-mshttp://ms.dbpedia.org/resource/
dbpedia-arhttp://ar.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
n54http://www.cs.princeton.edu/theory/complexity/
n31http://tl.dbpedia.org/resource/
n42http://dbpedia.org/resource/Wikt:
dbpedia-frhttp://fr.dbpedia.org/resource/
n15http://commons.wikimedia.org/wiki/Special:FilePath/
dctermshttp://purl.org/dc/terms/
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n22http://d-nb.info/gnd/
n63http://portal.acm.org/
n17http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
dbpedia-euhttp://eu.dbpedia.org/resource/
xsdhhttp://www.w3.org/2001/XMLSchema#
n26http://people.cs.uchicago.edu/~fortnow/papers/
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
n11https://mathoverflow.net/q/
n29https://www.scottaaronson.com/papers/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-skhttp://sk.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-rohttp://ro.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbpedia-nlhttp://nl.dbpedia.org/resource/
yago-reshttp://yago-knowledge.org/resource/
n49https://global.dbpedia.org/id/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
n20http://ast.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-simplehttp://simple.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
n61https://www.worldscientific.com/worldscibooks/10.1142/11270%7Cdoi=10.1142/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Computational_complexity_theory
rdf:type
owl:Thing yago:Arrangement105726596 yago:WikicatAlgorithms yago:YagoPermanentlyLocatedEntity yago:Cognition100023271 yago:Event100029378 yago:Act100030358 yago:PsychologicalFeature100023100 yago:Rule105846932 yago:Activity100407535 yago:DataStructure105728493 yago:Algorithm105847438 yago:Abstraction100002137 yago:Procedure101023820 yago:Structure105726345 yago:WikicatDataStructures dbo:Organisation
rdfs:label
Computationele complexiteitstheorie Komplexitätstheorie Teoria de la complexitat computacional Θεωρία πολυπλοκότητας Теорія складності обчислень Теория сложности вычислений Teorie složitosti 計算複雜性理論 Teoría de la complejidad computacional 計算複雑性理論 Teoria della complessità computazionale Computational complexity theory نظرية التعقيد الحسابي Théorie de la complexité (informatique théorique) Konplexutasun konputazionalaren teoria 계산 복잡도 이론
rdfs:comment
계산 복잡도 이론(計算 複雜度 理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. 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. 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. Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. 计算复杂性理论(Computational complexity theory)是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题,亦即这个问题可以用一系列机械的数学步骤解决,例如算法。 如果一个问题的求解需要相当多的资源(无论用什么算法),则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源(时间和空间),从而将资源的确定方法正式化了。其他复杂性测度同样被运用,比如通信量(应用于通信复杂性),电路中门的数量(应用于电路复杂性)以及中央处理器的数量(应用于并行计算)。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域,与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量,而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说,它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地,在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标:后者关心的是何种问题原则上可以用算法解决。 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. Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. 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. 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. 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. نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. 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. Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. 計算複雑性理論(けいさんふくざつせいりろん、英: computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。 「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 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.​ 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é.
rdfs:seeAlso
dbr:Combinatorial_explosion
foaf:depiction
n15:Decision_Problem.svg n15:TSP_Deutschland_3.png n15:Complexity_classes.svg n15:Complexity_subsets_pspace.svg n15:Sorting_quicksort_anim.gif n15:Turing_machine_2b.svg
dcterms:subject
dbc:Computational_complexity_theory dbc:Computational_fields_of_study
dbo:wikiPageID
7543
dbo:wikiPageRevisionID
1120968876
dbo:wikiPageWikiLink
dbr:Prime_factorization dbr:AC_(complexity) dbr:Quantum_complexity_theory dbr:Probabilistic_Turing_machine dbr:Co-NP dbr:Polynomial-time_reduction dbr:P_(complexity) dbr:Protein_structure_prediction dbr:BPP_(complexity) dbr:Quantum_Turing_machine dbr:Switching_theory dbr:ALL_(complexity) dbr:NP-complete dbr:Optimization_problem dbr:NP-hard dbr:Non-deterministic_time dbr:Quantum_algorithm dbr:Discrete_uniform_distribution dbr:Sharp-P dbr:Raymond_Smullyan dbr:Circuit_complexity dbr:Hisao_Yamada dbr:Connectivity_(graph_theory) dbr:BQP dbr:Knapsack_problem dbr:Cobham's_thesis dbr:John_Myhill dbr:Boolean_satisfiability_problem dbr:Complement_(complexity) dbr:General_number_field_sieve dbr:Deterministic_Turing_machine dbr:Space_hierarchy_theorem n17:Turing_machine_2b.svg dbr:Discrete_logarithm_problem dbr:Gabriel_Lamé dbr:Leaf_language dbr:Operations_research dbr:Mathematical_optimization dbr:Integer_factorization_problem dbr:Graph_(discrete_mathematics) dbr:Descriptive_complexity_theory dbr:PSPACE dbr:Graph_theory dbr:Mathematics dbr:Complete_(complexity) dbr:SAT_solver dbr:NTIME dbr:Church–Turing_thesis dbr:RAM_machine dbr:NL_(complexity) dbr:Computational_problem dbr:EXPSPACE dbr:Adjacency_list dbr:Adjacency_matrix dbr:Traveling_salesman_problem dbr:RSA_(algorithm) dbr:Juris_Hartmanis dbr:Log-space_reduction dbr:Differential_equation dbr:Parallel_computing dbr:Richard_E._Stearns dbr:Time_hierarchy_theorem dbr:NSPACE dbr:Alternating_Turing_machine dbr:Best,_worst_and_average_case dbr:Numerical_analysis dbr:NPSPACE dbr:Milan dbr:Cobham–Edmonds_thesis dbr:List_of_important_publications_in_theoretical_computer_science dbr:Blum's_speedup_theorem dbr:ZPP_(complexity) dbr:Presburger_arithmetic dbr:Models_of_computation dbr:Boolean_circuit dbr:PP_(complexity) dbr:Quicksort dbr:Savitch's_theorem dbr:Randomized_algorithm dbr:Context_of_computational_complexity dbr:Blum_axioms dbr:Binary_notation dbr:Complexity dbr:Alan_Turing dbr:Eugene_Luks dbr:Theoretical_computer_science dbr:Counting_problem_(complexity) dbr:FP_(complexity) dbr:List_of_computability_and_complexity_topics dbr:Boris_Trakhtenbrot dbr:Logic_gate dbr:Vertex_cover_problem dbr:Limits_of_computation dbr:Computer dbr:Manuel_Blum dbr:Function_problem dbr:Communication_complexity n17:TSP_Deutschland_3.png dbr:Big_O_notation n17:Sorting_quicksort_anim.gif dbr:Graph_isomorphism dbr:Graph_isomorphism_problem dbr:Time_complexity dbr:Blum_complexity_axioms dbr:Hamiltonian_path_problem dbr:Conway's_Game_of_Life dbr:P_versus_NP_problem dbr:Computational_complexity dbr:Computational_complexity_of_mathematical_operations dbr:Non-deterministic_Turing_machine dbr:Information_based_complexity dbr:Stephen_Cook dbc:Computational_complexity_theory dbr:Analysis_of_algorithms n42:infeasible dbr:Transcomputational_problem dbr:NEXPSPACE n42:intractable dbr:Symmetric_Turing_machine dbr:IP_(complexity) dbr:Random-access_machine dbr:Parameterized_complexity dbr:Shor's_algorithm dbr:Decision_tree_complexity dbr:Proof_complexity dbr:Turing_machine_equivalents dbr:DTIME dbr:Formal_language dbr:Lambda_calculus dbr:NP_(complexity) n17:Complexity_classes.svg dbc:Computational_fields_of_study dbr:Cellular_automata dbr:Axiom dbr:Integer_programming dbr:RP_(complexity) dbr:Age_of_the_universe dbr:Analog_computation dbr:Euclidean_algorithm dbr:Biology dbr:Polynomial_time_hierarchy n17:Complexity_subsets_pspace.svg dbr:Logistics dbr:Polynomial_time dbr:Amortized_analysis dbr:Feasible_solution dbr:Total_function dbr:QMA dbr:Promise_problem dbr:Space_complexity dbr:Richard_Karp dbr:String_(computer_science) dbr:Clay_Mathematics_Institute dbr:Dynamical_system dbr:List_of_unsolved_problems_in_computer_science dbr:Decision_problem dbr:NEXPTIME dbr:NC_(complexity) dbr:Control_theory dbr:Millennium_Prize_Problems dbr:Bitstring dbr:Non-deterministic_algorithm dbr:Primality_testing dbr:Interactive_proof_system dbr:Linear_bounded_automata dbr:Alphabet_(computer_science) dbr:L_(complexity) dbr:Pure_mathematics dbr:Game_complexity dbr:Linear_time dbr:Computability_theory dbr:NP-intermediate n17:Decision_Problem.svg dbr:DSPACE dbr:Probability_distribution dbr:List_of_complexity_classes dbr:Deterministic_algorithm dbr:Algorithm dbr:Cook–Levin_theorem dbr:Structural_complexity_theory dbr:Monotone_circuit dbr:Leonid_Levin dbr:László_Babai dbr:Jack_Edmonds dbr:Combinatorics dbr:EXPTIME dbr:Integer dbr:AM_(complexity)
dbo:wikiPageExternalLink
n11:34487 n26:history.pdf n29:philos.pdf n30:Complexity_Zoo n36:cc-book.html n47:0,11855,5-0-22-1519914-0,00.html n54: n61:11270 n63:citation.cfm%3Fid=800191.805573
owl:sameAs
dbpedia-nl:Computationele_complexiteitstheorie dbpedia-no:Kompleksitetsteori dbpedia-he:תורת_הסיבוכיות dbpedia-zh:計算複雜性理論 dbpedia-tr:Hesaplamalı_karmaşıklık_teorisi n20:Teoría_de_la_complexidá_computacional dbpedia-vi:Lý_thuyết_độ_phức_tạp_tính_toán n22:4120591-1 wikidata:Q205084 dbpedia-es:Teoría_de_la_complejidad_computacional dbpedia-de:Komplexitätstheorie dbpedia-it:Teoria_della_complessità_computazionale dbpedia-sh:Računska_teorija_složenosti n31:Teorya_ng_komputasyonal_na_komplehidad dbpedia-simple:Computational_complexity_theory dbpedia-hr:Računska_teorija_složenosti dbpedia-fa:نظریه_پیچیدگی_محاسباتی dbpedia-ja:計算複雑性理論 freebase:m.023z_ dbpedia-eu:Konplexutasun_konputazionalaren_teoria dbpedia-th:ทฤษฎีความซับซ้อนในการคำนวณ dbpedia-cs:Teorie_složitosti dbpedia-ko:계산_복잡도_이론 dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-ru:Теория_сложности_вычислений dbpedia-bg:Теория_на_изчислителната_сложност n49:woAX dbpedia-ar:نظرية_التعقيد_الحسابي dbpedia-sr:Теорија_комплексности yago-res:Computational_complexity_theory dbpedia-el:Θεωρία_πολυπλοκότητας dbpedia-uk:Теорія_складності_обчислень dbpedia-ca:Teoria_de_la_complexitat_computacional dbpedia-ro:Teoria_complexității n59:পরিগণনামূলক_জটিলতা_তত্ত্ব dbpedia-sk:Teória_zložitosti dbpedia-ms:Teori_kekompleksan_pengiraan
dbp:wikiPageUsesTemplate
dbt:Computer_science dbt:Commonscat dbt:Main dbt:See_also dbt:Dead_link dbt:Harv dbt:Wikt dbt:Use_mdy_dates dbt:Reflist dbt:Springer dbt:Short_description dbt:Garey-Johnson dbt:Authority_control dbt:Quote dbt:ComplexityClasses dbt:Div_col dbt:Div_col_end dbt:Citation dbt:Visible_anchor
dbo:thumbnail
n15:TSP_Deutschland_3.png?width=300
dbp:bot
InternetArchiveBot
dbp:date
January 2022
dbp:fixAttempted
yes
dbp:id
p/c130160
dbp:title
Computational complexity classes
dbo:abstract
Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально визначених моделей обчислювальних пристроїв. Складність алгоритмів вимірюється за необхідними ресурсами, в основному це тривалість обчислень або необхідний обсяг пам'яті. В окремих випадках досліджуються інші міри складності, такі як розмір мікросхем, або кількість процесорів, необхідна для роботи паралельних алгоритмів. Слід не плутати теорію складності обчислень з теорією обчислюваності, яка займається пошуком відповіді на запитання про те, які задачі можуть бути взагалі розв'язані за допомогою алгоритмів. Основна задача досліджень в теорії складності обчислень полягає у класифікації всіх розв'язних задач. Зокрема, робляться спроби відокремити множину задач з ефективними алгоритмами розв'язання від множини важко розв'язних задач. 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. 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é. 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. 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. 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. 计算复杂性理论(Computational complexity theory)是理论计算机科学和数学的一个分支,它致力于将可计算问题根据它们本身的复杂性分类,以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题,亦即这个问题可以用一系列机械的数学步骤解决,例如算法。 如果一个问题的求解需要相当多的资源(无论用什么算法),则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源(时间和空间),从而将资源的确定方法正式化了。其他复杂性测度同样被运用,比如通信量(应用于通信复杂性),电路中门的数量(应用于电路复杂性)以及中央处理器的数量(应用于并行计算)。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域,与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量,而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说,它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地,在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标:后者关心的是何种问题原则上可以用算法解决。 計算複雑性理論(けいさんふくざつせいりろん、英: computational complexity theory)とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性(計算問題の困難さ)などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。 「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。 계산 복잡도 이론(計算 複雜度 理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다. 복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다. 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. Η θεωρία πολυπλοκότητας είναι το μέρος εκείνο της θεωρίας υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της και κεντρικό γνωστικό πεδίο της επιστήμης υπολογιστών. Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο χρόνος, οπότε μιλάμε για τη χρονική πολυπλοκότητα του αλγορίθμου, δηλαδή πόσα «βήματα» χρειάζεται να εκτελέσει ο αλγόριθμος συναρτήσει της του, και ο χώρος, οπότε μιλάμε για τη χωρική πολυπλοκότητα, δηλαδή πόσο χώρο (μνήμη) χρειάζεται ο αλγόριθμος συναρτήσει της εισόδου του. Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι παράλληλοι επεξεργαστές χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα. نظرية التعقيد هي فرع من فروع نظرية الحوسبة والرياضيات، وهذه النظرية تتركز في تصنيف المسائل الحاسوبية حسب صعوبتها وربط أقسام التعقيد (complexity classes) ببعضها، والمسألة الحاسوبية هي المسألة التي يستطيع الحاسوب بحلها. ويمكن اعتبارها مسألة صعبة إذا استخدمت كمية مُعينة من الموارد أياً كانت الخوارزمية. ولعل النماذج الحسابية هي الطريقة الأمثل في هذه النظرية لدراسة هذه المسائل وتحديد كمية الموارد اللازمة مثل: الوقت أو حجم المكان الإضافي اللازم، وتوجد معايير تعقيد أخرى مثل: الاتصال (مستخدم في نظرية تعقيد الاتصال) وعدد البوابات في الدارات المنطقية (مستخدم في نظرية تعقيد الدارات المنطقية) وكذلك عدد المعالجات (مستخدم في الحساب المتوازي). وأحد أهم أساسيات نظرية التعقيد الحسابي هي إظهار الحدود العملية لما يستطيع الحاسوب القيام به وما لا يستطيع القيام به. المجالات القريبة في علم الحاسوب النظري هي تحليل الخوارزميات ونظرية الحاسوبية، والفرق بين تحليل الخوارزميات ونظرية التعقيد الحسابية هو أن الأول يسأل عن خوارزمية معينة لحل مسألة، بينما الآخر يسأل عن كل الخوارزميات التي يمكنها حل المسألة، وبالتحديد فإن الأخير يحاول تصنيف المسائل التي يمكن حلها أو عدم حلها بوضع كمية مُحددة من الموارد، أما وضع الحدود للموارد الموجودة هو ما يميز نظرية التعقيد الحسابي عن النظرية الحاسوبية أي أن النظرية الحاسوبية تسأل عن أية مسائل يمكن حلها بواسطة خوارزمية. 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. 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. Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов. Следует не путать теорию сложности вычислений с теорией вычислимости, которая занимается поиском ответа на вопрос о том, какие задачи могут быть вообще решены с помощью алгоритмов. Основная задача исследований в теории сложности вычислений заключается в классификации всех разрешимых задач. В частности, делаются попытки разделить множество задач с эффективными алгоритмами решения от множества трудно разрешимых задач. 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.
gold:hypernym
dbr:Branch
prov:wasDerivedFrom
wikipedia-en:Computational_complexity_theory?oldid=1120968876&ns=0
dbo:wikiPageLength
49963
foaf:isPrimaryTopicOf
wikipedia-en:Computational_complexity_theory