We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially computational complexity theory. We will discuss the PCP Theorem, its implications to inapproximability o...
详细信息
We briefly survey a number of important recent uchievements in Theoretical Computer Science （TCS）, especially computational complexity theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant＇s new theory of holographic algorithms and reductions.
In the framework of Membrane Computing, several tools to tackle the P versus NP problems by means of frontiers of the efficiency expressed in terms of syntactic or semantic ingredients, have been developed. In this pa...
详细信息
In the framework of Membrane Computing, several tools to tackle the P versus NP problems by means of frontiers of the efficiency expressed in terms of syntactic or semantic ingredients, have been developed. In this paper, an overview of the results in computational complexity theory concerning to membrane systems (tissue-like and cell-like approach) with symport/antiport rules (where objects are transported without evolving), is given. The frontiers are formulated regarding the length of communication rules, the kind of rules implementing the production of an exponential number of cells/membranes in polynomial time, and the role of the environment. An interesting remark of the obtained results refers that the underlying structure to membrane systems (directed graph versus rooted tree) does not matter in this context.
Most cipher systems designed thus far are binary-valued or integer-valued cipher systems. Their security relies on the assumption that one-way functions exist. Though the existence of one-way functions has not been pr...
详细信息
Most cipher systems designed thus far are binary-valued or integer-valued cipher systems. Their security relies on the assumption that one-way functions exist. Though the existence of one-way functions has not been proved yet, most cryptographic researchers believe that one-way functions exist. In addition, many candidates for one-way functions have been proposed. Therefore, the key step for developing real-valued cipher systems is to define real one-way functions and to propose candidates for them. In this paper, based on computational complexity theory over the real field, we give two definitions of real one-way functions; one is for digital one-way functions and the other is for general one-way functions. Candidates for these two classes of one-way functions are also proposed. Moreover, we present two examples to demonstrate that the candidates for both digital one-way functions and general one-way functions can be applied to construct secure real-valued cipher systems.
P systems are computing devices based on sets of rules that dictate how they work. While some of these rules can change the objects within the system, other rules can even change the own structure, like creation rules...
详细信息
P systems are computing devices based on sets of rules that dictate how they work. While some of these rules can change the objects within the system, other rules can even change the own structure, like creation rules. They have been used in cell-like membrane systems with active membranes to efficiently solve NP-complete problems. In this work, we improve a previous result where a uniform family of P systems with evolutional communication rules whose left-hand side (respectively, right-hand side) have most 2 objects (resp., 2 objects) and membrane creation solved SAT efficiently, and we obtain an efficient solution to solve QBF-SAT or QSAT (a PSPACE-complete problem) having at most 1 object (respectively, 1 object) in their left-hand side (resp., right-hand side) and not making use of the environment. (C) 2022 Elsevier B.V. All rights reserved.
作者：
Ikeda, KazukiLowe, AdamSUNY Stony Brook
Codesign Ctr Quantum Advantage C2QA Stony Brook CO 11794 USA SUNY Stony Brook
Ctr Nucl Theory Dept Phys & Astron Stony Brook NY 11794 USA Aston Univ
Coll Engn & Phys Sci Sch Informat & Digital Engn Birmingham B4 7ET England
We present a simple quantum interactive proof (QIP) protocol using the quantum state teleportation and quantum energy teleportation (QET) protocols. QET is a technique that allows a receiver at a distance to extract t...
详细信息
We present a simple quantum interactive proof (QIP) protocol using the quantum state teleportation and quantum energy teleportation (QET) protocols. QET is a technique that allows a receiver at a distance to extract the local energy by local operations and classical communication (LOCC), using the energy injected by the supplier as collateral. QET works for any local Hamiltonian with entanglement and, for our study, it is important that getting the ground state of a generic local Hamiltonian is quantum Merlin-Arthur-hard. The key motivations behind employing QET for these purposes are clarified. Firstly, in cases where a prover possesses the correct state and executes the appropriate operations, the verifier can effectively validate the presence of negative energy with a high probability (completeness). Failure to select the appropriate operators or an incorrect state renders the verifier incapable of observing negative energy (soundness). Importantly, the verifier solely observes a single qubit from the prover's transmitted state, while remaining oblivious to the prover's Hamiltonian and state (zero-knowledge). Furthermore, the analysis is extended to distributed quantum interactive proofs, where we propose multiple solutions for the verification of each player's measurement. The results in the N-party scenario could have particular relevance for the implementation of future quantum networks, where verification of quantum information is a necessity. The complexity class of our protocol in the most general case belongs to QIP(3)=PSPACE;hence, it provides a secure quantum authentication scheme that can be implemented in small quantum communication devices. It is straightforward to extend our protocol to Quantum Multi-Prover Interactive Proof (QMIP) systems, where the complexity is expected to be more powerful (PSPACE subset of\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepack
We introduce the boolean hierarchy of k-partitions over NP for k >= 3 as a generalization of the boolean hierarchy of sets (i.e., 2-partitions) over NP. Whereas the structure of the latter hierarchy is rather simpl...
详细信息
We introduce the boolean hierarchy of k-partitions over NP for k >= 3 as a generalization of the boolean hierarchy of sets (i.e., 2-partitions) over NP. Whereas the structure of the latter hierarchy is rather simple the structure of the boolean hierarchy of k-partitions over NP for k >= 3 turns out to be much more complicated. We formulate the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results. (c) 2007 Elsevier Inc. All rights reserved.
Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities i...
详细信息
Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from "classical" algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan-Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 2017).
Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely w...
详细信息
Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the polynomial hierarchy. In particular, we prove that, for k >2, if P-Sigma kp[1] = P Sigma(kp[2]) then Sigma(k)(p) = Pi(k)(p) = PH. We extend this to obtain a more general downward collapse result.
We study the effect of query order on computational power and show that P-BH j[1]:BHk[1] -the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by on...
详细信息
We study the effect of query order on computational power and show that P-BH j[1]:BHk[1] -the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by one query to the kth level of the boolean hierarchy-equals R-j+2k-1-tt(p) (NP) if j is even and k is odd and equals R-j+2k-tt(p) (NP) otherwise. Thus unless the polynomial hierarchy collapses it holds that, for each 1 less than or equal to j less than or equal to k, P-BH j[1]:BHk[1] = P-BH k[1]:BH j[1] double left right arrow (j = k) boolean OR (j is even boolean AND k = j + 1). We extend our analysis to apply to more general query classes.
We place many computational problems over solvable black-box groups in the counting complexity classes SPP or LWPP. The classes SPP and LWPP are considered classes of low counting complexity. In particular, SPP is low...
详细信息
We place many computational problems over solvable black-box groups in the counting complexity classes SPP or LWPP. The classes SPP and LWPP are considered classes of low counting complexity. In particular, SPP is low (powerless when used as oracles) for all gap-definable counting classes (PP, C=P, Mod(k)P, etc.) and LWPP is low for PP and C=P. The results improve the upper bounds for these problems proved in [Arvind and Vinodchandran, Theoret. Comput. Sci., 180 (1997), pp. 17-45], where the authors place these problems in randomized versions of SPP and LWPP. Because of the randomization, upper bounds in that paper implied lowness only for the class PP. The results in this paper favor the belief that these problems are unlikely to be complete for NP.
暂无评论