共查询到20条相似文献,搜索用时 26 毫秒
1.
Every Linear Threshold Function has a Low-Weight Approximator 总被引:1,自引:1,他引:0
Rocco A. Servedio 《Computational Complexity》2007,16(2):180-209
2.
M. S. Barketau T. C. E. Cheng C. T. Ng Vladimir Kotov Mikhail Y. Kovalyov 《Journal of Scheduling》2008,11(1):17-28
In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a step function
depending on its waiting time, which is the time between the start of the processing of the batch to which the job belongs
and the start of the processing of the job. For job i, if its waiting time is less than a given threshold value D, then it requires a basic processing time a
i
; otherwise, it requires an extended processing time a
i
+b
i
. The objective is to minimize the completion time of the last job. We first show that the problem is NP-hard in the strong
sense even if all b
i
are equal, it is NP-hard even if b
i
=a
i
for all i, and it is non-approximable in polynomial time with a constant performance guarantee Δ<3/2, unless
. We then present O(nlog n) and O(n
3F−1log n/F
F
) algorithms for the case where all a
i
are equal and for the case where there are F, F≥2, distinct values of a
i
, respectively. We further propose an O(n
2log n) approximation algorithm with a performance guarantee
for the general problem, where m
* is the number of batches in an optimal schedule. All the above results apply or can be easily modified for the corresponding
open-end bin packing problem. 相似文献
3.
In this paper, we address a fundamental problem related to the induction of Boolean logic: Given a set of data, represented as a set of binary “truen-vectors” (or “positive examples”) and a set of “falsen-vectors” (or “negative examples”), we establish a Boolean function (or an extension)f, so thatfis true (resp., false) in every given true (resp., false) vector. We shall further require that such an extension belongs to a certain specified class of functions, e.g., class of positive functions, class of Horn functions, and so on. The class of functions represents our a priori knowledge or hypothesis about the extensionf, which may be obtained from experience or from the analysis of mechanisms that may or may not cause the phenomena under consideration. The real-world data may contain errors, e.g., measurement and classification errors might come in when obtaining data, or there may be some other influential factors not represented as variables in the vectors. In such situations, we have to give up the goal of establishing an extension that is perfectly consistent with the given data, and we are satisfied with an extensionfhaving the minimum number of misclassifications. Both problems, i.e., the problem of finding an extension within a specified class of Boolean functions and the problem of finding a minimum error extension in that class, will be extensively studied in this paper. For certain classes we shall provide polynomial algorithms, and for other cases we prove their NP-hardness. 相似文献
4.
The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is called the inversion complexity of f. In 1958, Markov determined the inversion complexity of every Boolean function and, in particular, proved that log2(n+1) NOT gates are sufficient to compute any Boolean function on n variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs. 相似文献
5.
Ann argument function,f, is calledt-private if there exists a distributed protocol for computingf so that no coalition of at mostt processors can infer any additional information from the execution of the protocol. It is known that every function defined over a finite domain is [(n–1)/2]-private. The general question oft-privacy (fort[n/2]) is still unresolved.In this work, we relate the question of [n/2]-privacy for the class of symmetric functions of Boolean argumentsf: {0, 1}
n
{0, 1,...,n} to the structure of Hamming weights inf
–1(b) (b{0, 1, ...,n}). We show that iff is [n/2]-private, then every set of Hamming weightsf
–1(b) must be an arithmetic progression. For the class ofdense symmetric functions (defined in the sequel), we refine this to the following necessary and sufficient condition for [n/2]-privacy off: Every collection of such arithmetic progressions must yield non-identical remainders, when computed modulo the greatest common divisor of their differences. This condition is used to show that for dense symmetric functions, [n/2]-privacy impliesn-privacy. 相似文献
6.
7.
V. V. Bayev 《Problems of Information Transmission》2008,44(3):243-265
The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field GF(2 n ), as well as for larger classes of functions defined by their trace forms. In particular, for n ≥ 5, the algebraic immunity of the function Tr n (x ?1) has a lower bound ?2√n + 4? ? 4, which is close enough to the previously obtained upper bound ?√n? + ?n/?√n?? ? 2. We obtain a polynomial algorithm which, give a trace form of a Boolean function f, computes generating sets of functions of degree ≤ d for the following pair of spaces. Each function of the first (linear) space bounds f from below, and each function of the second (affine) space bounds f from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables. 相似文献
8.
Every Boolean function may be represented as a real polynomial. In this paper, we characterize the degree of this polynomial in terms of certain combinatorial properties of the Boolean function. Our first result is a tight lower bound of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables. Our second result states that for every Boolean functionf, the following measures are all polynomially related: o The decision tree complexity off. o The degree of the polynomial representingf. o The smallest degree of a polynomialapproximating f in theL max norm. 相似文献
9.
Ingo Wegener 《Acta Informatica》1981,15(2):147-152
Summary Circuit depth is an important complexity measure for a Boolean function. Let some Boolean function of n variables have depth k according to an arbitrary binary basis . For each j where [log n]jk we prove the existence of a Boolean function f with the following properties. f depends essentially on n variables and the depth of f according to is exactly j Thus we state the best possible hierarchy result on the depth of all nondegenerate Boolean functions. 相似文献
10.
Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics.
We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}n → {0, 1} which depend on all n variables, and distinct primes p, q:
o If f has degree o(log n) modulo p, then it must have degree Ω(n1−o(1)) modulo q. Thus a Boolean function has degree o(log n) in at most one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. 相似文献
11.
Halfspace Matrices 总被引:1,自引:1,他引:0
Alexander A. Sherstov 《Computational Complexity》2008,17(2):149-178
12.
The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various
mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory
(
). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of
by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient (namely, polynomial) quantum
algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e
2π
i/5, and moreover, that this problem is
-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et al.
are heavily based on
, which makes the algorithm essentially inaccessible to computer scientists.
We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n strands braid with m crossings at any primitive root of unity e
2π
i/k
, where the running time of the algorithm is polynomial in m, n and k. Our algorithm is based, rather than on
, on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of
the Markov trace for the Temperley-Lieb algebra). By the results of Freedman et al., our algorithm solves a
complete problem.
Our algorithm works by encoding the local structure of the problem into the local unitary gates which are applied by the circuit.
This structure is significantly different from previous quantum algorithms, which are mostly based on the Quantum Fourier
transform. Since the results of the current paper were presented in their preliminary form, these ideas have been extended
and generalized in several interesting directions. Most notably, Aharonov, Arad, Eban and Landau give a simplification and
extension of these results that provides additive approximations for all points of the Tutte polynomial, including the Jones
polynomial at any point, and the Potts model partition function at any temperature and any set of coupling strengths. We hope
and believe that the ideas presented in this work will have other extensions and generalizations. 相似文献
13.
We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an additive error of at most ε using as few samples of f as possible. We use the adaptive framework: on all problem instances an adaptive algorithm should perform almost as well
as the best possible algorithm tuned for the particular problem instance. We distinguish between
and
, the performances of the best possible deterministic and randomized algorithms, respectively. We give a deterministic algorithm
that uses
samples and show that an asymptotically better algorithm is impossible. However, any deterministic algorithm requires
samples on some problem instance. By combining a deterministic adaptive algorithm and Monte Carlo sampling with variance reduction,
we give an algorithm that uses at most
samples. We also show that any algorithm requires
samples in expectation on some problem instance (f,ε), which proves that our algorithm is optimal. 相似文献
14.
This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes Dp and pSAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship. 相似文献
15.
It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log2
N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs
of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs.
One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably
simple and combinatorially clear. Other examples have the additional property that f is in AC0.
Received: June 5 1997. 相似文献
16.
17.
Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional
to binary decision diagram) that each variable is tested at most once during the computation. The function EARn is the following Boolean function defined for n × n Boolean matrices: EARn(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EARn has size at least
and we present a construction of such diagrams of size approximately
. 相似文献
18.
Xueling Ma Jianming Zhan Yang Xu 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2007,11(11):1079-1087
In this paper, we introduce the notions of interval valued -fuzzy filters and interval valued -fuzzy Boolean (implicative) filters in R
0-algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters
are derived. In particular, we prove that an interval valued fuzzy set F in R
0-algebras is an interval valued -fuzzy Boolean filter if and only if it is an interval valued -fuzzy implicative filter. 相似文献
19.
In this paper, we define double Horn functions, which are the Boolean functionsfsuch that bothfand its complement (i.e., negation)fare Horn, and investigate their semantical and computational properties. Double Horn functions embody a balanced treatment of positive and negative information in the course of the extension problem of partially defined Boolean functions (pdBfs), where a pdBf is a pair (T, F) of disjoint setsT, F⊆{0, 1}nof true and false vectors, respectively, and an extension of (T, F) is a Boolean functionfthat is compatible withTandF. We derive syntactic and semantic characterizations of double Horn functions, and determine the number of such functions. The characterizations are then exploited to give polynomial time algorithms (i) that recognize double Horn functions from Horn DNFs (disjunctive normal forms), and (ii) that compute the prime DNF from an arbitrary formula, as well as its complement and its dual. Furthermore, we consider the problem of determining a double Horn extension of a given pdBf. We describe a polynomial time algorithm for this problem and moreover an algorithm that enumerates all double Horn extensions of a pdBf with polynomial delay. However, finding a shortest double Horn extension (in terms of the size of a formula?representing it) is shown to be intractable. 相似文献
20.
The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n. 相似文献
|