共查询到20条相似文献,搜索用时 62 毫秒
1.
We show that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or even nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i)
(ii) Permanent is not computable by polynomial-size arithmetic circuits. We also prove a (partial) converse: If Permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic circuit of polynomially bounded degree computes an identically zero polynomial.Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If
then NEXP is not computable by polynomial-size arithmetic circuits. Thus establishing that RP = coRP or BPP = P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits. We also show that any derandomization of RNC would yield new circuit lower bounds for a language in NEXP.We also prove unconditionally that NEXPRP does not have polynomial-size Boolean or arithmetic circuits. Finally, we show that
if both BPP = P and low-degree testing is in P; here low-degree testing is the problem of checking whether a given Boolean circuit computes a function that is close to some low-degree polynomial over a finite field. 相似文献
2.
A syntactic read-k-times branching program has the restriction that no variable occurs more thank times on any path (whether or not consistent) of the branching program. We first extend the result in [31], to show that the “n/2 clique only function”, which is easily seen to be computable by deterministic polynomial size read-twice programs, cannot be computed by nondeterministic polynomial size read-once programs, although its complement can be so computed. We then exhibit an explicit Boolean functionf such that every nondeterministic syntactic read-k-times branching program for computingf has size exp $$\left( {\Omega \left( {\frac{n}{{4^k k^3 }}} \right)} \right).$$ 相似文献
3.
Emanuele Viola 《Computational Complexity》2005,13(3-4):147-188
We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function
computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant
such that every circuit of size
fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a
computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies
under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function
(i.e. there is a constant
such that every circuit of size
fails to compute f on some input) for every positive constant
there is no black-box construction of a
computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes. 相似文献
4.
Relations between states and maps, which are known for quantum systems in finitedimensional Hilbert spaces, are formulated
rigorously in geometrical terms with no use of coordinate (matrix) interpretation. In a tensor product realization they are
represented simply by a permutation of factors. This leads to natural generalizations for infinite-dimensional Hilbert spaces
and a simple proof of a generalized Choi Theorem. The natural framework is based on spaces of Hilbert-Schmidt operators and the corresponding tensor products of Hilbert spaces. It is proved that the corresponding isomorphisms cannot be naturally extended to compact (or bounded)
operators, nor reduced to the trace-class operators. On the other hand, it is proven that there is a natural continuous map
from trace-class operators on (with the nuclear norm) into compact operators mapping the space of all bounded operators on into trace class operators on (with the operator-norm). Also in the infinite-dimensional context, the Schmidt measure of entanglement and multipartite
generalizations of state-maps relations are considered in the paper. 相似文献
5.
Iwona Cieślik 《Acta Informatica》2008,45(2):79-91
Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for
-free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs. 相似文献
6.
7.
8.
Jiří Močkoř 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2009,13(6):591-596
We investigate interpretations of formulas ψ in a first order fuzzy logic in models which are based on objects of a category SetR(Ω) which consists of Ω-sets, i.e. sets with similarity relations with values in a complete MV-algebra Ω and with morphisms
defined as special fuzzy relations between Ω-sets. The interpretations are then morphisms in a category SetR(Ω) from some Ω-set to the object . We define homomorphisms between models in a category SetR(Ω) and we prove that if is a (special) homomorphism of models in a category SetR(Ω) then there is a relation between interpretations of a formula ψ in models .
Supported by MSM6198898701, grant 201/07/0191 of GAČR and grant 1M0572. 相似文献
9.
Antoine Chaillet Yacine Chitour Antonio Loría Mario Sigalotti 《Mathematics of Control, Signals, and Systems (MCSS)》2008,20(2):135-156
Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question:
is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator.
Notation A continuous function is of class
, if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class
-function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L
2-norm of matrices. 相似文献
10.
This paper deals with multidimensional systems, for example, systems described by linear, constant coefficient partial differential/difference
equations. In the behavioral approach, the notion of interconnection is the basis of control. In this setting, feedback interconnection
of systems is based on the still more fundamental concept of regular interconnection, which has been introduced by J.C. Willems.
The dual problem of regular interconnection is the one of direct sum decomposition. The following two problems are addressed:
given a behavior and one of its sub-behaviors , under what conditions does there exist another sub-behavior such that has finite dimension and has finite codimension with respect to i.e. we treat the direct sum decomposition of up to finite-dimensional behaviors, which, in this context, are considered negligible. The second related problem concerns
regular interconnections and reads as follows: given a plant behavior together with a desired behavior, find, if possible,
another behavior (a controller) such that the interconnection is regular and has finite codimension with respect to the given
desired behavior. A constructive solution to the problems is provided for two-dimensional behaviors. 相似文献
11.
This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints: where \(N \ge 2\), \(f_i\) are convex functions, \(A_i\) are matrices, and \({\mathcal {X}}_i\) are feasible sets for variable \(\mathbf{x}_i\). Our algorithm extends the alternating direction method of multipliers (ADMM) and decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This paper shows that the classic ADMM can be extended to the N-block Jacobi fashion and preserve convergence in the following two cases: (i) matrices \(A_i\) are mutually near-orthogonal and have full column-rank, or (ii) proximal terms are added to the N subproblems (but without any assumption on matrices \(A_i\)). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that \(\Vert {\mathbf {x}}^{k+1} - {\mathbf {x}}^k\Vert _M^2\) converges at a rate of o(1 / k) where M is a symmetric positive semi-definte matrix. Since the parameters used in the convergence analysis are conservative, we introduce a strategy for automatically tuning the parameters to substantially accelerate our algorithm in practice. We implemented our algorithm (for the case ii above) on Amazon EC2 and tested it on basis pursuit problems with >300 GB of distributed data. This is the first time that successfully solving a compressive sensing problem of such a large scale is reported.
相似文献
$$\begin{aligned} \text {minimize} ~~&f_1(\mathbf{x}_1) + \cdots + f_N(\mathbf{x}_N)\\ \text {subject to}~~&A_1 \mathbf{x}_1 ~+ \cdots + A_N\mathbf{x}_N =c,\\&\mathbf{x}_1\in {\mathcal {X}}_1,~\ldots , ~\mathbf{x}_N\in {\mathcal {X}}_N, \end{aligned}$$
12.
13.
Mohammad Ali Abam Mark de Berg Mohammad Farshi Joachim Gudmundsson Michiel Smid 《Algorithmica》2011,61(1):207-225
Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function:
$\mathbf{d}_{\omega}(p,q)=\left\{{ll}0&\mbox{ if $\mathbf{d}_{\omega}(p,q)=\left\{\begin{array}{ll}0&\mbox{ if 相似文献
14.
The Sum of D Small-Bias Generators Fools Polynomials of Degree D 总被引:1,自引:1,他引:0
Emanuele Viola 《Computational Complexity》2009,18(2):209-217
15.
Simple a posteriori error estimators for the <Emphasis Type="Italic">h</Emphasis>-version of the boundary element method 总被引:1,自引:0,他引:1
The h-h/2-strategy is one well-known technique for the a posteriori error estimation for Galerkin discretizations of energy minimization
problems. One considers to estimate the error , where is a Galerkin solution with respect to a mesh and is a Galerkin solution with respect to the mesh obtained from a uniform refinement of . This error estimator is always efficient and observed to be also reliable in practice. However, for boundary element methods,
the energy norm is non-local and thus the error estimator η does not provide information for a local mesh-refinement. We consider Symm’s integral equation of the first kind, where the
energy space is the negative-order Sobolev space . Recent localization techniques allow to replace the energy norm in this case by some weighted L
2-norm. Then, this very basic error estimation strategy is also applicable to steer an h-adaptive algorithm. Numerical experiments in 2D and 3D show that the proposed method works well in practice. A short conclusion
is concerned with other integral equations, e.g., the hypersingular case with energy space and , respectively, or a transmission problem.
Dedicated to Professor Ernst P. Stephan on the occasion of his 60th birthday. 相似文献
16.
Fully discrete potential-based finite element methods called methods are used to solve a transient eddy current problem in a three-dimensional convex bounded polyhedron. Using methods, fully discrete coupled and decoupled numerical schemes are developed. The existence and uniqueness of solutions
for these schemes together with the energy-norm error estimates are provided. To verify the validity of both schemes, some
computer simulations are performed for the model from TEAM Workshop Problem 7.
This work was supported by Postech BSRI Research Fund-2009, National Basic Research Program of China (2008CB425701), NSFC
under the grant 10671025 and the Key Project of Chinese Ministry of Education (No. 107018). 相似文献
17.
Michell cantilevers constructed within trapezoidal domains—Part II: virtual displacement fields 总被引:1,自引:1,他引:0
The present second part of the paper deals with the virtual displacement fields associated with the optimality conditions , where σ
T and σ
C represent the allowable values of the tensile and compressive stress, respectively. The displacement fields vanish along a straight segment of a line support and are constructed within an infinite domain bounded by two half-lines. The displacement fields are provided by the integral formulae involving the Lamé fields found in part I of this paper. All the results are expressed in terms of Lommel-like functions. These results make it possible to determine the volumes of the optimal cantilevers designs within the feasible domain considered. Computation of the volumes along with analyses of concrete cantilevers will be the subject of part IV of the present paper. 相似文献
18.
Hierarchical matrices (
-matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for
-matrices is almost optimal. In this paper we present an algebraic approach for constructing
-matrices which combines multilevel clustering methods with
-matrix arithmetic to compute the
-inverse,
-LU, and the
-Cholesky factors of a matrix. Then the
-inverse,
-LU or
-Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical
results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or
AMG, for solving some large, sparse linear systems, and is comparable to other
-matrix constructions based on Nested Dissection. 相似文献
19.
Félix Bou Francesco Paoli Antonio Ledda Hector Freytes 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(4):341-352
The present paper is a sequel to Paoli F, Ledda A, Giuntini R, Freytes H (On some properties of QMV algebras and QMV algebras, submitted). We provide two representation results for quasi-MV algebras in terms of MV algebras enriched with
additional structure; we investigate the lattices of subvarieties and subquasivarieties of quasi-MV algebras; we show that
quasi-MV algebras, as well as cartesian and flat quasi-MV algebras, have the amalgamation property. 相似文献
|