Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.     

Lower bound of overall exponential sums for polynomialsϕ(x d )

LetS ⁽¹⁾ (n, Q) denote the maximum module of exponential sums for polynomials of degree n over the Galois fieldF _Q . In a previous paper the transition to the multiple exponential sums allowed us to obtain a good lower bound of the valueS ⁽¹⁾ (n, Q), which coincides with Weil's bound whenn = q ^(m-1)/2 + 1, whereq, m are odd andm 3. Here the same approach is used for the estimation of the valueS ^(d) (n, Q), which corresponds to polynomials(x ^d ) overF _Q , whered is any divisor ofq – 1.     

On the width of an orientation of a tree

There are 2 ^n-1 ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these posets are determined. The maximal width depends on the bipartition of the tree as a bipartite graph and it can be determined in time O(n). The minimal width is one of [/2] or [/2]+1, where is the number of leaves of the tree. An algorithm of execution time O(n + ² log ) to construct the minimal width orientation is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

Dual vectors and lower bounds for the nearest lattice point problem

We prove that given a point outside a given latticeL then there is a dual vector which gives a fairly good estimate for how far from the lattice the vector is. To be more precise, there is a set of translated hyperplanesH _i, such thatL _iH_i andd( _iH_i)(6n ²+1)^–1 d( ,L).Supported by an IBM fellowship.     

The gap between monotone and non-monotone circuit complexity is exponential

A. A. Razborov has shown that there exists a polynomial time computable monotone Boolean function whose monotone circuit complexity is at leastn ^{c losn} . We observe that this lower bound can be improved to exp(cn ^1/6–o(1)). The proof is immediate by combining the Alon—Boppana version of another argument of Razborov with results of Grötschel—Lovász—Schrijver on the Lovász — capacity, of a graph.     

基于褐藻酸钠-纳米金复合物作非酶标记的新型电化学免疫传感器的研制

比较了用三碘甲状腺氨酸抗体(T3抗体)、褐藻酸钠(AS)标记T3抗体及褐藻酸钠-纳米金复合物(ASN)标记的T3抗体,在通过免疫反应结合到免疫电极表面后,引起的电极表面微环境发生改变的程度;用Fe(CN)3-/4-6为电化学探针,用循环伏安法获取金电极表面微环境改变的电流信息来检测 T3抗体,检测的线性范围为100～1 600ng·ml-1,检出限为45ng·ml-1.     

Some developments in reaction and solution microcalorimetry,with particular reference to its use in biochemistry and cellular biology

The field of isothermal microcalorimetry as applied to systems of interest for aqueous solution chemistry, biochemistry and in cellular biology is briefly reviewed. Some techniques recently developed in the author's laboratory are described.