Dissertations / Theses on the topic 'Computational complexity and computability'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Computational complexity and computability.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Latsch, Wolfram Wilhelm. "Beyond complexity and evolution : on the limits of computability in economics." Thesis, University of Oxford, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.325103.
Full textPouly, Amaury. "Continuous models of computation: from computability to complexity." Palaiseau, Ecole polytechnique, 2015. https://theses.hal.science/tel-01223284/document.
Full textPégny, Maël. "Sur les limites empiriques du calcul : calculabilité, complexité et physique." Thesis, Paris 1, 2013. http://www.theses.fr/2013PA010673/document.
Full textRecent years have seen a surge in the interest for non-standard computational models, inspired by physical, biological or chemical phenomena. The exact properties of some of these models have been a topic of somewhat heated discussion: what do they compute? And how fast do they compute? The stakes of these questions were heightened by the claim that these models would violate the accepted limits of computation, by violating the Church-Turing Thesis or the Extended Church-Turing Thesis. To answer these questions, the physical realizability of some of those models - or lack thereof - has often been put at the center of the argument. It thus seems that empirical considerations have been introduced into the very foundations of computability and computational complexity theory, both subjects that would have been previously considered purely a priori parts of logic and computer science. Consequently, this dissertation is dedicated to the following question: do computability and computational complexity theory rest on empirical foundations? If yes, what are these foundations? We will first examine the precise meaning of those limits of computation, and articulate a philosophical conception of computation able to make sense of this variety of models. We then answer the first question by the affirmative, through a careful examination of current debates around non-standard models. We show the various difficulties surrounding the second question, and study how they stem from the complex translation of computational concepts into physical limitations
Kübel, David J. F. [Verfasser]. "On some Geometric Search Problems : Algorithms, Complexity, Computability / David J. F. Kübel." Bonn : Universitäts- und Landesbibliothek Bonn, 2020. http://d-nb.info/1224270606/34.
Full textFarr, Graham E. "Topics in computational complexity." Thesis, University of Oxford, 1986. http://ora.ox.ac.uk/objects/uuid:ad3ed1a4-fea4-4b46-8e7a-a0c6a3451325.
Full textVikas, Narayan. "Computational complexity of graph compaction." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq24360.pdf.
Full textYamakami, Tomoyuki. "Average case computational complexity theory." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq28091.pdf.
Full textTseng, Hung-Li. "Computational Complexity of Hopfield Networks." Thesis, University of North Texas, 1998. https://digital.library.unt.edu/ark:/67531/metadc278272/.
Full textRubiano, Thomas. "Implicit Computational Complexity and Compilers." Thesis, Sorbonne Paris Cité, 2017. http://www.theses.fr/2017USPCD076/document.
Full textLa théorie de la complexité´e s’intéresse à la gestion des ressources, temps ou espace, consommés par un programmel ors de son exécution. L’analyse statique nous permet de rechercher certains critères syntaxiques afin de catégoriser des familles de programmes. L’une des approches les plus fructueuses dans le domaine consiste à observer le comportement potentiel des données manipulées. Par exemple, la détection de programmes “non size increasing” se base sur le principe très simple de compter le nombre d’allocations et de dé-allocations de mémoire, en particulier au cours de boucles et on arrive ainsi à détecter les programmes calculant en espace constant. Cette méthode s’exprime très bien comme propriété sur les graphes de flot de contrôle. Comme les méthodes de complexité implicite fonctionnent à l’aide de critères purement syntaxiques, ces analyses peuvent être faites au moment de la compilation. Parce qu’elles ne sont ici que statiques, ces analyses ne sont pas toujours calculables ou facilement calculables, des compromis doivent être faits en s’autorisant des approximations. Dans le sillon du “Size-Change Principle” de C. S. Lee, N. D. Jones et A. M. Ben-Amram, beaucoup de recherches reprennent cette méthode de prédiction de terminaison par observation de l’évolution des ressources. Pour le moment, ces méthodes venant des théories de la complexité implicite ont surtout été appliquées sur des langages plus ou moins jouets. Cette thèse tend à porter ces méthodes sur de “vrais” langages de programmation en s’appliquant au niveau des représentations intermédiaires dans des compilateurs largement utilises. Elle fournit à la communauté un outil permettant de traiter une grande quantité d’exemples et d’avoir une idée plus précise de l’expressivité réelle de ces analyses. De plus cette thèse crée un pont entre deux communautés, celle de la complexité implicite et celle de la compilation, montrant ainsi que chacune peut apporter à l’autre
Okabe, Yasuo. "Parallel Computational Complexity and Date-Transfer Complexity of Supercomputing." Kyoto University, 1994. http://hdl.handle.net/2433/74658.
Full textQuttineh, Nils-Hassan. "Computational Complexity of Finite Field Multiplication." Thesis, Linköping University, Department of Electrical Engineering, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-1968.
Full textThe subject for this thesis is to find a basis which minimizes the number of bit operations involved in a finite field multiplication. The number of bases of a finite field increases quickly with the extension degree, and it is therefore important to find efficient search algorithms. Only fields of characteristic two are considered.
A complexity measure is introduced, in order to compare bases. Different methods and algorithms are tried out, limiting the search in order to explore larger fields. The concept of equivalent bases is introduced.
A comparison is also made between the Polynomial, Normal and Triangular Bases, referred to as known bases, as they are commonly used in implementations. Tables of the best found known bases for all fields up to GF(2^24) is presented.
A list of the best found bases for all fields up to GF(2^25) is also given.
Edwards, K. "Topics in computational complexity and enumeration." Thesis, University of Oxford, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.376892.
Full textAlfonsin, Jorge L. Ramirez. "Topics in combinatorics and computational complexity." Thesis, University of Oxford, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.334189.
Full textMelkebeek, Dieter van. "Randomness and completeness in computational complexity." New York : Springer, 2000. http://www.springerlink.com/openurl.asp?genre=issue&issn=0302-9743&volume=1950.
Full textPontoizeau, Thomas. "Community detection : computational complexity and approximation." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLED007/document.
Full textThis thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, I study four different definitions of a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, I study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs
Parisen, Toldin Paolo <1984>. "Implicit computational complexity and probabilistic classes." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amsdottorato.unibo.it/5573/1/Parisen_Toldin_Paolo_tesi.pdf.
Full textParisen, Toldin Paolo <1984>. "Implicit computational complexity and probabilistic classes." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amsdottorato.unibo.it/5573/.
Full textWareham, Harold Todd. "Systematic parameterized complexity analysis in computational phonology." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ37368.pdf.
Full textBull, David R. "Signal processing techniques with reduced computational complexity." Thesis, Cardiff University, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.388006.
Full textNoel, Jonathan A. "Extremal combinatorics, graph limits and computational complexity." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b.
Full textDare, Christopher Edward. "Turing Decidability and Computational Complexity of MorseHomology." Thesis, Virginia Tech, 2019. http://hdl.handle.net/10919/90397.
Full textMaster of Science
With the growing prevalence of data in the technological world, there is an emerging need to identify geometric properties (such as holes and boundaries) to data sets. However, it is often fruitless to employ an algorithm if it is known to be too computationally expensive (or even worse, not computable in the traditional sense). However, discrete Morse theory was originally formulated to provide a simplified manner of calculating these geometric properties on discrete sets. Therefore, this thesis outlines the general background of Discrete Morse theory and formulates the computational cost of computing specific geometric algorithms from the Discrete Morse perspective.
Hagen, Matthias. "Algorithmic and computational complexity issues of MONET." Göttingen Cuvillier, 2008. http://d-nb.info/99226300X/04.
Full textZuppiroli, Sara <1979>. "Probabilistic Recursion Theory and Implicit Computational Complexity." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amsdottorato.unibo.it/6723/1/thesis.pdf.
Full textZuppiroli, Sara <1979>. "Probabilistic Recursion Theory and Implicit Computational Complexity." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amsdottorato.unibo.it/6723/.
Full textBovo, Samuele <1989>. "Development of computational methods for biological complexity." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amsdottorato.unibo.it/8366/1/SB_thesis_2018.pdf.
Full textLemieux, François 1961. "Finite groupoids and their applications to computational complexity." Thesis, McGill University, 1996. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=40171.
Full textWe consider different restrictions on the original model. We examine the effect of restricting the kind of groupoids used, the way parentheses are placed, and we distinguish between the case where parentheses are explicitly given and the case where they are guessed nondeterministically.
We introduce the notions of linear recognition by groupoids and by programs over groupoids. This leads to new characterizations of linear context-free languages and NL. We also prove that the algebraic structure of finite groupoids induces a strict hierarchy on the classes of languages they linearly recognized.
We investigate the classes obtained when the groupoids are restricted to be quasigroups (i.e. the multiplication table forms a latin square). We prove that languages recognized by quasigroups are regular and that programs over quasigroups characterize NC$ sp1$.
We also consider the problem of evaluating a well-parenthesized expression over a finite loop (a quasigroup with an identity). This problem is in NC$ sp1$ for any finite loop, and we give algebraic conditions for its completeness. In particular, we prove that it is sufficient that the loop be nonsolvable, extending a well-known theorem of Barrington.
Finally, we consider programs where the groupoids are allowed to grow with the input length. We study the relationship between these programs and more classical models of computation like Turing machines, pushdown automata, and owner-read owner-write PRAM. As a consequence, we find a restriction on Boolean circuits that has some interesting properties. In particular, circuits that characterize NP and NL are shown to correspond, in presence of our restriction, to P and L respectively.
Kamath, Pritish. "Some hardness escalation results in computational complexity theory." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/128290.
Full textThesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2020
Cataloged from student-submitted PDF of thesis. "February 2020."
Includes bibliographical references (pages 92-105).
In this thesis, we prove new hardness escalation results in computational complexity theory; a phenomenon where hardness results against seemingly weak models of computation for any problem can be lifted, in a black box manner, to much stronger models of computation by considering a simple gadget composed version of the original problem. For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols. This allows us to prove new lower bounds for: -- Monotone Circuit Size : we get an exponential lower bound for an explicit monotone function computable by linear sized monotone span programs and also in (non-monotone) NC². -- Real Monotone Circuit Size : Our proof technique extends to real communication protocols, which yields similar lower bounds against real monotone circuits. -- Cutting Planes Length : we get exponential lower bound for an explicit CNF contradiction that is refutable with logarithmic Nullstellensatz degree. Finally, we describe an intimate connection between computational models and communication complexity analogs of the sub-classes of TFNP, the class of all total search problems in NP. We show that the communication analog of PPA[subscript p] captures span programs over F[subscript p] for any prime p. This complements previously known results that communication FP captures formulas (Karchmer- Wigderson, 1988) and that communication PLS captures circuits (Razborov, 1995).
by Pritish Kamath.
Ph. D.
Ph.D. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
McQuillan, Colin. "The computational complexity of approximation of partition functions." Thesis, University of Liverpool, 2013. http://livrepository.liverpool.ac.uk/12893/.
Full textAghighi, Meysam. "Computational Complexity of some Optimization Problems in Planning." Doctoral thesis, Linköpings universitet, Programvara och system, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-136280.
Full textGoussevskaia, Olga. "Computational complexity and scheduling algorithms for wireless networks." Konstanz Hartung-Gorre, 2009. http://d-nb.info/997891122/04.
Full textSabharwal, Ashish. "Algorithmic applications of propositional proof complexity /." Thesis, Connect to this title online; UW restricted, 2005. http://hdl.handle.net/1773/6938.
Full textKawachi, Akinori. "Studies on quantum query complexity and quantum computational cryptography." 京都大学 (Kyoto University), 2004. http://hdl.handle.net/2433/145315.
Full text0048
新制・課程博士
博士(情報学)
甲第11157号
情博第132号
新制||情||30(附属図書館)
22726
UT51-2004-R32
京都大学大学院情報学研究科通信情報システム専攻
(主査)教授 岩間 一雄, 教授 福嶋 雅夫, 教授 北野 正雄
学位規則第4条第1項該当
De, Benedetti Erika. "Linear logic, type assignment systems and implicit computational complexity." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL0981/document.
Full textIn this thesis we explore the linear logic approach to implicit computational complexity, through the design of type assignment systems based on light linear logic, or heavily inspired by them, with the purpose of giving a characterization of one or more complexity classes, through variants of lambda-calculi which are typable in such systems. In particular, we consider both a monovalent and a polyvalent perspective with respect to ICC. In the first one the aim is to characterize a hierarchy of complexity classes through an elementary lambda-calculus typed in Elementary Linear Logic (ELL), where the complexity depends only on the interface of a term, namely its type. The second approach gives an account of both the functions computable in polynomial time and of strong normalization, through terms of pure lambda-calculus which are typed in a system inspired by Soft Linear Logic (SLL); in particular, with respect to the usual logical take, in the latter we give up the “!” modality in favor of employing stratified types as a refinement of non-associative intersection types, in order to improve typability and, as a consequence, expressivity.Finally we explore the use of intersection types, deprived of some of their usual properties, towards a more quantitative approach rather than the usual qualitative one, namely in order to compute a bound on the computation of pure lambda-terms, obtaining in addition a characterization of strong normalization
Fomenko, Fedor. "Dual-context multicategories as models for implicit computational complexity." Thesis, University of Edinburgh, 2008. http://hdl.handle.net/1842/29104.
Full textHallett, Michael Trevor. "An integrated complexity analysis of problems from computational biology." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1996. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq21933.pdf.
Full textBroxvall, Mathias. "A Study in the Computational Complexity of Temporal Reasoning." Doctoral thesis, Linköping : Univ, 2002. http://www.ep.liu.se/diss/science_technology/07/79/index.html.
Full textTesson, Pascal. "Computational complexity questions related to finite monoids and semigroups." Thesis, McGill University, 2003. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=84441.
Full textWe first consider the "program over monoid" model of D. Barrington and D. Therien [BT88] and set out to answer two fundamental questions: which monoids are rich enough to recognize arbitrary languages via programs of arbitrary length, and which monoids are so weak that any program over them has an equivalent of polynomial length? We find evidence that the two notions are dual and in particular prove that every monoid in DS has exactly one of these two properties. We also prove that for certain "weak" varieties of monoids, programs can only recognize those languages with a "neutral letter" that can be recognized via morphisms over that variety.
We then build an algebraic approach to communication complexity, a field which has been of great importance in the study of small complexity classes. We prove that every monoid has communication complexity O(1), &THgr;(log n) or &THgr;(n) in this model. We obtain similar classifications for the communication complexity of finite monoids in the probabilistic, simultaneous, probabilistic simultaneous and MOD p-counting variants of this two-party model and thus characterize the communication complexity (in a worst-case partition sense) of every regular language in these five models. Furthermore, we study the same questions in the Chandra-Furst-Lipton multiparty extension of the classical communication model and describe the variety of monoids which have bounded 3-party communication complexity and bounded k-party communication complexity for some k. We also show how these bounds can be used to establish computational limitations of programs over certain classes of monoids.
Finally, we consider the computational complexity of testing if an equation or a system of equations over some fixed finite monoid (or semigroup) has a solution.
Smith, Justin N. "Computational complexity, bounded rationality and the theory of games." Thesis, University of Oxford, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.365642.
Full textChandoo, Maurice [Verfasser]. "Computational complexity aspects of implicit graph representations / Maurice Chandoo." Hannover : Gottfried Wilhelm Leibniz Universität Hannover, 2018. http://d-nb.info/117241436X/34.
Full textLevy, Matthew Asher. "A SURVEY OF LIMITED NONDETERMINISM IN COMPUTATIONAL COMPLEXITY THEORY." UKnowledge, 2003. http://uknowledge.uky.edu/gradschool_theses/221.
Full textArasteh, Davoud. "Computational Intelligence and Complexity Measures for Chaotic Information Processing." ScholarWorks@UNO, 2008. http://scholarworks.uno.edu/td/834.
Full textHolder, Ethan Graham. "Musiplectics: Computational Assessment of the Complexity of Music Scores." Thesis, Virginia Tech, 2015. http://hdl.handle.net/10919/52376.
Full textMaster of Science
Shah, Kushal Yogeshkumar. "Computational Complexity of Signal Processing Functions in Software Radio." Cleveland State University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=csu1292854939.
Full textKotzing, Timo. "Abstraction and complexity in computational learning in the limit." Access to citation, abstract and download form provided by ProQuest Information and Learning Company; downloadable PDF file, 156 p, 2009. http://proquest.umi.com/pqdweb?did=1886744841&sid=7&Fmt=2&clientId=8331&RQT=309&VName=PQD.
Full textVee, Erik. "Time-space tradeoffs for nonuniform computation /." Thesis, Connect to this title online; UW restricted, 2004. http://hdl.handle.net/1773/6915.
Full textDandekar, Pranav. "Algebraic-geometric methods for complexity lower bounds." [Gainesville, Fla.] : University of Florida, 2004. http://purl.fcla.edu/fcla/etd/UFE0008843.
Full textPavan, A. "Average-case complexity theory and polynomial-time reductions." Buffalo, N.Y. : Dept. of Computer Science, State University of New York at Buffalo, 2001. http://www.cse.buffalo.edu/tech%2Dreports/2001%2D10.ps.Z.
Full textLee, Yoonhyoung Gordon Peter C. "Linguistic complexity and working memory structure effect of the computational demands of reasoning on syntactic complexity /." Chapel Hill, N.C. : University of North Carolina at Chapel Hill, 2007. http://dc.lib.unc.edu/u?/etd,797.
Full textTitle from electronic title page (viewed Dec. 18, 2007). "... in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Psychology (Cognitive Psychology)." Discipline: Psychology; Department/School: Psychology.
Neyer, Gabriele. "Algorithms, complexity, and software engineering in computational geometry : case studies /." [S.l.] : [s.n.], 2000. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=13586.
Full textHundt, Christian [Verfasser]. "On the computational complexity of projective image matching / Christian Hundt." Lübeck : Zentrale Hochschulbibliothek Lübeck, 2012. http://d-nb.info/1020437006/34.
Full text