检索结果-内蒙古大学图书馆

circuit complexity of Regular Languages

THEORY OF COMPUTING SYSTEMS 2009年第4期45卷 865-879页

作者： Koucky, Michal Acad Sci Czech Republ Inst Math CR-11567 Prague 1 Czech Republic

We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in AC(0) and ACC(0) are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222-234, 1985). As a consequence we obtain that in order to separate ACC(0) from NC1 it suffices to prove for some epsilon > 0 an Omega(n (1+epsilon) ) lower bound on the size of ACC(0) circuits computing certain NC1-complete functions.

关键词： Regular languages circuit complexity Upper and lower bounds

来源：评论

学校读者我要写书评

暂无评论

circuit complexity of linear functions: Gate elimination and feeble security

引用

Journal of Mathematical Sciences (United States) 2013年第1期188卷 35-46页

作者： Davydow, A.P. Nikolenko, S.I. St. Petersburg Academic University St. Petersburg Russian Federation St. Petersburg Department of the Steklov Mathematical Institute St. Petersburg Russian Federation

In this paper, we consider provably secure cryptographic constructions in the context of circuit complexity. Based on the ideas of provably secure trapdoor functions developed in (Hirsch, Nikolenko, 2009;Melanich, 2009), we present a new linear construction of a provably secure trapdoor function with order of security 5/4. Besides, we present an in-depth general study of the gate elimination method for the case of linear functions. We also give a nonconstructive proof of lower bounds on the circuit complexity of linear Boolean functions and upper bounds on circuit implementations of linear Boolean functions, obtaining specific constants. Bibliography: 53 titles. © 2012 Springer Science+Business Media New York.

关键词： circuit complexity LINEAR systems BOUNDS (Mathematics) MATHEMATICAL constants MATHEMATICAL proofs BOOLEAN functions (Mathematics) MATHEMATICAL analysis

来源：评论

学校读者我要写书评

暂无评论

circuit complexity of regular languages

引用

3rd Conference on Computability in Europe (CiE 2007)

作者： Koucky, Michal Acad Sci Czech Republic Inst Math CZ-11567 Prague 1 Czech Republic

ISBN: (纸本)9783540730002

We survey our current knowledge of circuit complexity of regular languages. We show that regular languages are of interest as languages providing understanding of different circuit classes. We also prove that regular languages that are in AC(0) and ACC(0) are all computable by almost linear size circuits, extending the result of Chandra et al. [5].

关键词： regular languages circuit complexity

来源：评论

学校读者我要写书评

暂无评论

circuit complexity of k-Valued Logic Functions in One Infinite Basis

引用

Computational Mathematics and Modeling 2019年第1期30卷 13-25页

作者： Kochergin, V.V. Mikhailovich, A.V. Lomonosov Moscow State University and National Research University – Higher School of Economics Moscow Russian Federation National Research University – Higher School of Economics Moscow Russian Federation

We investigate the realization complexity of k -valued logic functions k 2 by combinational circuits in an infinite basis that includes the negation of the Lukasiewicz function, i.e., the function k−1−x, and all monotone functions. complexity is understood as the total number of circuit elements. For an arbitrary function f, we establish lower and upper complexity bounds that differ by at most by 2 and have the form 2 log (d(f) + 1) + o(1), where d(f) is the maximum number of times the function f switches from larger to smaller value (the maximum is taken over all increasing chains of variable tuples). For all sufficiently large n, we find the exact value of the Shannon function for the realization complexity of the most complex function of n variables. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

关键词： circuit complexity infinite basis inversion complexity logic circuits Markov theorem multi-valued logic functions non-monotone complexity

来源：评论

学校读者我要写书评

暂无评论

On the circuit complexity of sigmoid feedforward neural networks

引用

NEURAL NETWORKS 1996年第7期9卷 1155-1171页

作者： Beiu, V Taylor, JG King's College London LondonUK

This paper aims to examine the circuit complexity of sigmoid activation feedforward artificial neural networks by placing them amongst several classic Boolean and threshold gate circuit complexity classes. The starting point is the class NNk defined by Shawe-Taylor et al. (1992) Classes of feedforward neural nets and their circuit complexity. Neural Networks 5(6), 971-977. For a better characterisation, we introduce two additional classes NNDeltak and NNDelta,epsilonk, having less restrictive conditions than NNk concerning fan-in and accuracy, and proceed to prove relations amongst these three classes and well established circuit complexity classes. For doing that, a particular class of Boolean functions F-Delta is first introduced and we show how a threshold gate circuit can be recursively built for any f(Delta) belonging to F-Delta. As the G-functions (computing the carries) are f(Delta) functions, a class of solutions is obtained for threshold gate adders. We then constructively prove the inclusions amongst circuit complexity classes. This is done by converting the sigmoid feedforward artificial neural network into an equivalent threshold gate circuit (Shawe-Taylor et al., 1992). Each threshold gate is then replaced by a multiple input adder having a binary tree structure, relaxing the logarithmic fan-in condition from Shawe-Taylor et al. (1992) to (almost) polynomial. This means that larger classes of sigmoid activation feedforward neural networks can be implemented in polynomial size Boolean circuits with a small constant fan-in at the expense of a logarithmic factor increase in the number of layers. Similar results are obtained for threshold circuits, and are liked with the previous ones. The main conclusion is that there are interesting fan-in dependent depth-size tradeoffs when trying to digitally implement sigmoid activation feedforward neural networks. Copyright (C) 1996 Elsevier Science Ltd

关键词： neural networks threshold gate circuits Boolean circuits circuit complexity

来源：评论

学校读者我要写书评

暂无评论

A Note on a priori Estimations of Classification circuit complexity

引用

FUNDAMENTA INFORMATICAE 2010年第3期104卷 201-217页

作者： Albrecht, Andreas A. Chashkin, Alexander V. Iliopoulos, Costas S. Kasim-Zade, Oktay M. Lappas, Georgios Steinhoefel, Kathleen K. Kings Coll London Dept Comp Sci London WC2R 2LS England Queens Univ Belfast CCRCB Belfast Antrim North Ireland Moscow MV Lomonosov State Univ Fac Mech & Math Moscow Russia TEI Western Macedonia Kastoria Greece

The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to n(L) : = inverted right perpendicularlog(2) m(L)inverted left perpendicular, where m(L) is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) S(cc)(R) :=2 . root 2(nL)+3 gates for unbounded depth, (b) S(cc)(L) := 34.8 . root 2(nL) + 14 . n(L) - 11 . log(2) n(L) + 2 gates for small bounded depth, where in both cases all m(L) samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since n(L) < < n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that inverted right perpendicular1.25.S(cc)Rinverted left perpendicular or inverted right perpendicular0.07.S(cc)Linverted left perpendicular gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.

关键词： Threshold circuits neural network synthesis pattern classification circuit complexity sample size

来源：评论

学校读者我要写书评

暂无评论

Malign distributions for average case circuit complexity

引用

INFORMATION AND COMPUTATION 1999年第2期150卷 187-208页

作者： Jakoby, A Reischuk, R Schindelhauer, C Univ Lubeck Inst Theoret Informat D-23560 Lubeck Germany

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of all n-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at least n - log n - log log n expected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depth d, i.e. of worst case complexity d, the expected time complexity will be at least d - log n - log d with respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained. (C) 1999 Academic Press.

关键词： average complexity circuit complexity Boolean functions asymptotic complexity malign distributions lower bounds

来源：评论

学校读者我要写书评

暂无评论

Methods of class field theory to separate logics over finite residue classes and circuit complexity

引用

JOURNAL OF LOGIC AND COMPUTATION 2017年第7期27卷 1987-2009页

作者： Arratia, Argimiro Ortiz, Carlos E. Univ Politecn Cataluna Dept Comp Sci BGSMath Barcelona Spain Arcadia Univ Dept Comp Sci & Math Glenside PA USA

Separations among the first-order logic Res(0,+, x) of finite residue classes, its extensions with generalized quantifiers, and in the presence of a built-in order are shown in this article, using algebraic methods from class field theory. These methods include classification of spectra of sentences over finite residue classes as systems of congruences, and the study of their h-densities over the set of all prime numbers, for various functions h on the natural numbers. Over ordered structures, the logic of finite residue classes and extensions are known to capture DLOGTIME-uniform circuit complexity classes ranging from AC0 to TC0. Separating these circuit complexity classes is directly related to classifying the h-density of spectra of sentences in the corresponding logics of finite residue classes. General conditions are further shown in this work for a logic over the finite residue classes to have a sentence whose spectrum has no h-density. A corollary of this characterization of spectra of sentences is that in Res(0,+, x,<)+ M, the logic of finite residue classes with built-in order and extended with the majority quantifier M, there are sentences whose spectrum have no exponential density.

关键词： circuit complexity congruence classes density finite model theory prime spectra

来源：评论

学校读者我要写书评

暂无评论

Cosmological lower bound on the circuit complexity of a small problem in logic

引用

JOURNAL OF THE ACM 2002年第6期49卷 753-784页

作者： Stockmeyer, L Meyer, AR MIT Comp Sci Lab Cambridge MA 02139 USA IBM Corp Almaden Res Ctr San Jose CA USA

An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved: circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In particular, to decide the truth of logical formulas of length at most 610 in this second-order language requires a circuit containing at least 10(125) gates. So even if each gate were the size of a proton, the circuit would not fit in the known universe. This result and its proof, due to both authors, originally appeared in 1974 in the Ph.D. thesis of the first author. In this article, the proof is given, the result is put in historical perspective, and the result is extended to probabilistic circuits.

关键词： theory circuit complexity computational complexity decision problem logic lower bound practical undecidability WS1S

来源：评论

学校读者我要写书评

暂无评论

Reductions in circuit complexity: An isomorphism theorem and a gap theorem

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1998年第2期57卷 127-143页

作者： Agrawal, M Allender, E Rudich, S Indian Inst Technol Dept Comp Sci Kanpur 208016 Uttar Pradesh India Univ Ulm D-89069 Ulm Germany Rutgers State Univ Dept Comp Sci Piscataway NJ 08855 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

We show that all sets that are complete for NP under nonuniform AC(0) reductions are isomorphic under nonuniform AC(0)-computable isomorphisms. Furthermore, these sets remain NP-complete even under nonuniform NC0 reductions. More generally, we show two theorems that hold for any complexity class C closed under (uniform) NC1-computable many-one reductions. Gap: The sets that are complete for C under AC(0) and NC0 reducibility coincide. Isomorphism: The sets complete for C under AC(0) reductions are all isomorphic under isomorphisms computable and invertible by AC(0) circuits of depth three. Our Gap Theorem does not hold for strongly uniform reductions;we show that there are Dlogtime-uniform AC(0)-complete sets for NC1 that are not Dlogtime-uniform NC0-complete. (C) 1998 Academic Press.

关键词： One-way functions Conjecture Time Oracle Sets Np circuit complexity North Pacific Pattern one-way function Information retrieval systems-Teletext and videotex isomorphism Isomorphism theorems Nondeterministic polynomial-time hard Isomorphic Nonuniform Conjecture Theorem SETTING

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：