Some hardness escalation results in computational complexity theory per Kamath, Pritish.

Obtenir text complet

Extensions of Presburger arithmetic and model checking one-counter automata per Lechner, A

Matèries: “…Computational Complexity Theory…”

On nonintegral vertices of 3-SAT problem relaxation polytope per A. V. Nikolaev

Matèries: Obtenir text complet

P Systems with Evolutional Communication and Division Rules per David Orellana-Martín, Luis Valencia-Cabrera, Mario J. Pérez-Jiménez

Matèries: Obtenir text complet

18.404J / 6.840J Theory of Computation, Fall 2006 per Sipser, Michael

Matèries: “…Computability, computational complexity theory…”
Obtenir text complet

18.404J / 6.840J Theory of Computation, Fall 2002 per Sipser, Michael

Matèries: Obtenir text complet

Discrete Computation: Theory and Open Problems per Meyer, Albert R.

“…Borodin, A. Computational Complexity: Theory and Practice, in Currents in the Theory of Computing, A. …”
Obtenir text complet

The Spectral Norm of Finite Functions per Bellare, Mihir

“…In many recent results in learning and computational complexity theory which rely on Fourier analysis, the spectral norm plays a key role. …”
Obtenir text complet

A model-independent theory of computational complexity: from patience to precision and beyond per Blakey, E

“…<p>The field of computational complexity theory--which chiefly aims to quantify the difficulty encountered when performing calculations--is, in the case of conventional computers, correctly practised and well understood (some important and fundamental open questions notwithstanding); however, such understanding is, we argue, lacking when unconventional paradigms are considered. …”

Computational Complexity per J. A. Tenreiro Machado, António M. Lopes

“…The computational problems posed by CS exhibit intrinsic difficulties that are a major concern in Computational Complexity Theory. [...]…”
Obtenir text complet

Nonsequential Computation and Laws of Nature per Vitányi, Paul M.B.

“…Traditionally, computational complexity theory deals with sequential computations. …”
Obtenir text complet

QUANTUM DISCORD AND QUANTUM COMPUTING - AN APPRAISAL per Datta, A, Shaji, A

“…Completeness results from computational complexity theory lead to the identification of very disparate problems, and offer a kaleidoscopic view into the realm of quantum enhancements in computation. …”

Computational Structure of GPSG Models: Revised Generalized Phrase Structure Grammar per Ristad, Eric Sven

“…The primary goal of this report is to demonstrate how considerations from computational complexity theory can inform grammatical theorizing. …”
Obtenir text complet

Complexity of Computation of Dominating Sets in Geo-Mathmetics Algorithm : A Review per Şakir Işleyen

“…The dominant sets problem by testing whether γ (G) ≤ K of a given graph is G and K input; It is an electronic card NP machines decision problem in computational complexity theory. Infographics, powerful infographics plus graphic mapping. …”
Obtenir text complet

Incremental FPT Delay per Arne Meier

“…These results are the first direct connections of collapses in parameterized enumeration complexity to collapses in classical enumeration complexity, parameterized function complexity, classical function complexity, and computational complexity theory.…”
Obtenir text complet

The Complexity of Mental Integer Addition per Stefan Buijsman, Markus Pantsar

“…An important paradigm in modeling the complexity of mathematical tasks relies on computational complexity theory, in which complexity is measured through the resources (time, space) taken by a Turing machine to carry out the task. …”
Obtenir text complet

Contracting projected entangled pair states is average-case hard per Jonas Haferkamp, Dominik Hangleiter, Jens Eisert, Marek Gluza

“…In higher dimensions, however, a connection to the field of computational complexity theory has shown that the accurate normalization of the two-dimensional tensor networks called projected entangled pair states (PEPS) is #P-complete. …”
Obtenir text complet

A Survey of Noninteractive Zero Knowledge Proof System and Its Applications per Huixin Wu, Feng Wang

“…Zero knowledge proof system which has received extensive attention since it was proposed is an important branch of cryptography and computational complexity theory. Thereinto, noninteractive zero knowledge proof system contains only one message sent by the prover to the verifier. …”
Obtenir text complet

Task-independent metrics of computational hardness predict human cognitive performance per Juan Pablo Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts, Carsten Murawski

“…Here, building on insights from computational complexity theory, we quantify the computational hardness of cognitive tasks using a set of task-independent metrics related to the computational resource requirements of individual instances of a task. …”
Obtenir text complet

Unconventional complexity measures for unconventional computers per Blakey, E

“…One particular motivation behind unconventional computation is the desire efficiently to solve classically difficult problems—we recall chemical-computer attempts at solving NP-complete problems such as the Travelling Salesperson Problem—, with computational complexity theory offering the criteria for judging this efficiency. …”