20 papers · ranked by Valyu relevance
Jiangang Tang
This paper establishes the separation of complexity classes P and NP through a novel homological algebraic approach grounded in category theory. We construct the computational category Comp, embedding computational problems and reductions into a unified categorical framework. By developing computational homology…
Mor Weiss, Hemanta K. Maji
Probabilistically Checkable Proofs (PCPs) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form “ $x\inL$” by querying only a few proof bits. Zero-Knowledge PCPs (ZK-PCPs) enhance standard PCPs to additionally guarantee that the view of any…
Juan Pablo Franco, Peter Bossaerts, Carsten Murawski
Many everyday tasks require people to solve computationally complex problems. However, little is known about the effects of computational hardness on the neural processes associated with solving such problems. Here, we draw on computational complexity theory to address this issue. We performed an experiment in which…
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan
Strategy extraction is of great importance for quantified Boolean formulas (QBF), both in solving and proof complexity. So far in the QBF literature, strategy extraction has been algorithmically performed from proofs. Here we devise the first QBF system where (partial) strategies are built into the proof and are…
Constantine Kyritsis
It seems that at the beginning of each century has become a tradition to state a list of significant and usually difficult problems in the mathematics, that it is considered that their solution will advance significantly the mathematical sciences. At the begging of the 20th century (1900) it was D. Hilbert who…
Ciarán M. Lee, Matty J. Hoban
Quantum theory presents us with the tools for computational and communication advantages over classical theory. One approach to uncovering the source of these advantages is to determine how computation and communication power vary as quantum theory is replaced by other operationally defined theories from a broad…
Authors not listed
Step-by-step thinking is essential in all domains of chemical sciences and engineering. While machine learning tools are broadly used, algorithms that automate reasoning are far less common. We elaborate on seven categories of human reasoning activities and connect each to applications in chemical science and…
Romain D. Cazé
Multiple studies show how dendrites might extend some neurons’ computational capacity. These studies leave a large fraction of the nervous system unexplored. Here we demonstrate how a modest dendritic tree can allow cerebellar granule cells to implement linearly non-separable computations. Granule cells’ dendrites do…
John M. Myers, Hadi Madjid
The accurate copying of nucleotides in DNA replication is arguably a digital computation. So are some cognitive capacities found in all organisms. In 2005 we proved that linking quantum calculations to evidence requires guesswork subject to revision (Madjid and Myers [9]). Based on this proof, we assume computations by…
Gerald Friedland, Alfredo Metere
In this manuscript, we derive the principle of conservation of computational complexity. We measure computational complexity as the number of binary computations (decisions) required to solve a problem. Every problem then defines a unique solution space measurable in bits. For an exact result, decisions in the solution…
Angold Wang
Polynomials Authors: ['Angold Wang'] Abstract. This survey provides a comprehensive examination of verifiable computing, tracing its evolution from foundational complexity theory to modern zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs). We explore key developments in interactive proof…
Marius Krumm, Markus P. Müller, Michael Cuffaro, Stephan Hartmann
Can free agency be compatible with determinism? Compatibilists argue that the answer is yes, and it has been suggested that the computer science principle of “computational irreducibility” sheds light on this compatibility. It implies that there cannot, in general, be shortcuts to predict the behavior of agents…
Clare Horsman, Susan Stepney, Rob C. Wagner, Viv Kendon
Computing is a high-level process of a physical system. Recent interest in non-standard computing systems, including quantum and biological computers, has brought this physical basis of computing to the forefront. There has been, however, no consensus on how to tell if a given physical system is acting as a computer or…
Mårten Skogh, Phalgun Lolur, Werner Dobrautz, Christopher Warren + 5 more
There is currently no combination of quantum hardware and algorithms that can provide an advantage over conventional calculations of molecules or materials. However, if or when such a point is reached, new strategies will be needed to verify predictions made using quantum devices. We propose that the electron density…
Lorenzo Magnani
Eco-cognitive computationalism sees computation in context, exploiting the ideas developed in those projects that have originated the recent views on embodied, situated, and distributed cognition. Turing’s original intellectual perspective has already clearly depicted the evolutionary emergence in humans of…
Juan P. Franco, Karlo Doroc, Nitin Yadav, Peter Bossaerts + 1 more
The survival of human organisms depends on our ability to solve complex tasks in the face of limited cognitive resources. However, little is known about the factors that drive the complexity of those tasks. Here, building on insights from computational complexity theory, we quantify the computational hardness of…
Bhupinder Singh Anand
We distinguish finitarily between algorithmic verifiability, and algorithmic computability, to show that G¨odel's 'formally' unprovable, but 'numeral-wise' provable, arithmetical proposition [(∀x)R(x)] can be finitarily evidenced as: algorithmically verifiable as 'always' true, but not algorithmically computable as…
Attila Egri-Nagy
What is computable with limited resources? How can we verify the correctness of computations? How to measure computational power with precision? Despite the immense scientific and engineering progress in computing, we still have only partial answers to these questions. In order to make these problems more precise, we…
Eugene Christo V R, Christoph Robert Meinecke, Bert Nitzsche, Roman Lyttleton + 5 more
Network-based biocomputing (NBC) presents an energy-efficient, parallel computing approach for solving nondeterministic polynomial time (NP) complete problems by leveraging motor-driven cytoskeletal filaments that explore all possible solutions through nanofabricated networks in a massively parallel fashion. However…
Juan Prada, Johannes Balkenhol, Özge Osmanoglu, Maral Afshar + 6 more
Decisions in biology happen fast and are driven by evolution to optimize survival chances. In platelets, this is achieved by organizing signaling cascades into rapid decision-funnels with modulatory crosstalk. We show that network decision processes underlying cellular decisions are tough to solve (equivalent to…