The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.     

Onk-positive satisfiability problem

An algorithm for solving the satisfiability problem is presented. It is proved that this algorithm solves 2-SAT and Horn-SAT in linear time andk-positive SAT (in which every clause contains at mostk positive literals) in timeO(|F|·ξ _n ^k ), where |F| is the length of inputF, n is the number of atoms occurring inF, and ξ _k is the greatest real number satisfying the equation . Compared with previous results, this nontrivial upper bound on time complexity could only be obtained fork-SAT, which is a subproblem ofk-positive SAT. Research partially supported by NSFC grant 221-4-1439. HUANG Xiong received his B.S. and M.S. degrees in computer science from Peking University in 1992 and 1995 respectively. Now he is a Ph.D. candidate in Beijing University of Aeronautics and Astronautics. His major research interests are design and analysis of algorithms, computational complexity, and satisfiability problem. LI Wei received his B.S. degree in mathematics from Peking University in 1966 and his Ph.D. degree in computer science from The University of Edinburgh in 1983. Since 1986, he has been a Professor in computer science at Beijing University of Aeronautics and Astronautics. He has published over 100 papers in the areas of concurrent programming languages, operational semantics, type theory, and logical foundation of artificial intelligence.     

A further note on overshoot estimation in pole placements

Recently, it is proved in the literature that for a given controllable pair （A, B） with A ∈R^n×n, B ∈R^n×m, and any λ ≥ 1, a gain matrix K can be designed so that ‖e^（A＋BK）t‖ ≤Mλ^Le^-λt, where M and L are constants independent of λ. Here, we show that M and L can be chosen much smaller than that proposed above. As a consequence, the estimation on overshoot of a transition matrix can be bounded more precisely. This can be regarded as a complement to the existing result.     

A relationship between difference hierarchies and relativized polynomial hierarchies

Chang and Kadin have shown that if the difference hierarchy over NP collapses to levelk, then the polynomial hierarchy (PH) is equal to thekth level of the difference hierarchy over ₂ ^p . We simplify their poof and obtain a slightly stronger conclusion: if the difference hierarchy over NP collapses to levelk, then PH collapses to (P _(k–1) ^NP )^NP, the class of sets recognized in polynomial time withk – 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any classC that has _m ^p -complete sets and is closed under _conj ^p -and _m ^NP -reductions (alternatively, closed under _disj ^p -and _m ^co-NP -reductions), if the difference hierarchy overC collapses to levelk, then PH ^C = (P _(k–1)–tt ^NP ) ^C . Then we show that the exact counting class C_P is closed under _disj ^p - and _m ^co-NP -reductions. Consequently, if the difference hierarchy over C_P collapses to levelk, then PH^PP(= PH^C_P) is equal to (P _(k–1)–tt ^NP )^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.Finally we consider two ways of relativizing the bounded query class P _k–tt ^NP : the restricted relativization P _k–tt ^{NP C} and the full relativization (P _k–tt ^NP ) ^C . IfC is NP-hard, then we show that the two relativizations are different unless PH ^C collapses.Richard Beigel was supported in part by NSF Grants CCR-8808949 and CCR-8958528. Richard Chang was supported in part by NSF Research Grant CCR 88-23053. This work was done while Mitsunori Ogiwara was at the Department of Information Science, Tokyo Institute of Technology, Tokyo, Japan.     

On PAC learnability of functional dependencies

This paper proposes a kind of probably approximately correct (PAC) learning framework for inferring a set of functional dependencies (FDs) from example tuples. A simple algorithm is considered that outputs a set of all FDs which hold in a set of example tuples. Letr be a relation (a set of tuples). We define the error for a set of FDsFS as the minimum Σ _t∈ν; where ν (ν ⊂r) is a set such thatFS holds inr − ν, andP(t) denotes the probability that tuplet is picked fromr. Our attention is focused on the sample complexity, and we show that the number of example tuples required to infer a set of FDs whose error does not exceed ω with probability at least 1 − δ under an arbitrary probability distribution is. Tatsuya Akutsu, Ph. D.: He is an associate professor of Department of Computer Science, Gunma University. He received the B. E. degree in 1984, the M. E. degree in 1986 and the Dr. Eng. degree in 1989 from The University of Tokyo. From 1989 to 1994, he was with Mechanical Engineering Laboratory, MITI, Japan. His research interests are design and analysis of algorithms, computational learning theory and bioinformatics.     

Isomorphic Implication

We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, or is NP-complete, or is NP-hard, coNP-hard, and in P_‖^NP. We show how to extend the NP-hardness and coNP-hardness to P_‖^NP-hardness for some cases, and conjecture that this can be done in all cases. Supported in part by grants NSF-CCR-0311021 and DFG VO 630/5-1 and VO 630/5-2. An extended abstract of this paper appears in Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), pp. 119–130, Springer-Verlag Lecture Notes in Computer Science #3618, August 2005. Work of M. Bauland done in part while visiting CASCI’s Laboratory for Complexity at Rochester Institute of Technology. Work of E. Hemaspaandra done in part while on sabbatical at the University of Rochester.     

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to treelike resolution proofs. Therefore, lower bounds for treelike resolution (known since the 1960s) apply to them. However, these lower bounds say nothing about the behavior of such algorithms on satisfiable formulas. Proving exponential lower bounds for them in the most general setting is impossible without proving P ≠ NP; therefore, to prove lower bounds, one has to restrict the power of branching heuristics. In this paper, we give exponential lower bounds for two families of DPLL algorithms: generalized myopic algorithms, which read up to n ^1−ε of clauses at each step and see the remaining part of the formula without negations, and drunk algorithms, which choose a variable using any complicated rule and then pick its value at random. ^★Extended abstract of this paper appeared in Proceedings of ICALP 2004, LNCS 3142, Springer, 2004, pp. 84–96. ^†Supported by CCR grant CCR-0324906. ^‡Supported in part by Russian Science Support Foundation, RAS program of fundamental research “Research in principal areas of contemporary mathematics,” and INTAS grant 04-77-7173. ^§Supported in part by INTAS grant 04-77-7173.     

Risoluzione numerica di una disequazione variazionale

Riassunto Sia Ω un insieme aperto, connesso e limitato dello spazio euclideo reale adn dimensioni ℝ ⁿ . Sia ψ una funzione reale definita sulla chinsura di Ω e non positiva in prossimità della frontiera Γ di Ω. Presentiamo un metodo per la risoluzione numerica della disequazione variazionale dove ℝ={u∈H ₀ ¹ (Ω)|u≥ψ su ea(u, v) è una forma bilineare coercitiva sul sottospazioH ₀ ¹ (Ω) dello spazio reale di SobolevH ¹ (Ω).

---

Let Ω be an open, connected and bounded set of then-dimensional real Euclidean space ℝ ⁿ . Let ψ be a real function defined on the closure of Ω and non-positive near the boundary of Ω. We present a method for the numerical solution of the variational inequality where ℝ={u∈H ₀ ¹ (Ω)|u≥ψ on anda(u, v) is a bilinear form coercive on the subspaceH ₀ ¹ (Ω) of the real Sobolev spaceH ¹ (Ω).

     

Arthur and Merlin as Oracles

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) Arthur–Merlin class. Our main results are the following:

The Contiguity in R/M

An r.e. degree c is contiguous if degwtt(A)=degwtt(B)for any r.e. sets A,B∈c.In this paper,we generalize the notation of contiguity to the structure R/M, the upper semilattice of the r.e. degree set R modulo the cappable r.e. degree set M.An element[C]∈R/M is contiguous if s[degwtt(A)]=[degwtt(B)]for any r.e. sets A,B such that degT(A),degT(B)∈[c],It is proved in this paper that every nonzero element in R/M is not contiguous,i.e.,for every element [C]∈R/M,if[C]≠[O] then there exist at least two r.e. sets A,B such that degT(A),degT(B)∈[C]and [degwtt[A]≠[degwtt(B)].     

The 1-Versus-2 Queries Problem Revisited

The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient algorithm that makes at most 2 queries to a Σ _k ^p -complete language L _k has an efficient simulation that makes at most 1 query to L _k . We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that:

Finite Element Approximation of a Three Dimensional Phase Field Model for Void Electromigration

We consider a finite element approximation of a phase field model for the evolution of voids by surface diffusion in an electrically conducting solid. The phase field equations are given by the nonlinear degenerate parabolic system

Satisfiability of co-nested formulas

As a notion dual to Knuth's nested formulas [4], we call a boolean formula in conjunctive normal formco-nested if its clauses can be linearly ordered (sayC={c _i ;i=1,2, ...,n})so that the graphG ^cl =(XC, {xc _i ;xc _i or ¬xc _i } {c _i c _i+1;i=1, 2, ...,n}) allows a noncrossing drawing in the plane so that the circlec ₁,c ₂, ...,c _n bounds the outerface. Our main result is that maximum satisfiability of co-nested formulas can be decided in linear time.Both authors acknowledge a partial support of Ec Cooperative Action IC-1000 (project ALTEC:Algorithms for Future Technologies).     

Exact 3-satisfiability is decidable in time O(20.16254n)

Let F = C ₁ C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SAT O(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SAT O(2^0.16254n ).An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002).     

Disuguaglianze relative all'approssimazione polinomiale in norma uniforme

Let Π _n denote the space of algebraic polynomials of degreen or less. In this paper we establish the inequality for everyf _∈ C ⁽ⁿ⁻¹⁾ ([−1, 1]) andf ⁽ⁿ⁻¹⁾ absolutely continuous. A way for obtaining similar inequalities forf _∈ C ^(t−1) ([−1, 1]) andf ^(l−1) absolutely continuous is given.

---

---

Ricerca effettuata mentre l'autore fruiva di una Borsa di Studio del C.N.R.     

Generalized fuzzy bi-ideals of semigroups

After the introduction of fuzzy sets by Zadeh, there have been a number of generalizations of this fundamental concept. The notion of (∈, ∈ ∨q)-fuzzy subgroups introduced by Bhakat is one among them. In this paper, using the relations between fuzzy points and fuzzy sets, the concept of a fuzzy bi-ideal with thresholds is introduced and some interesting properties are investigated. The acceptable nontrivial concepts obtained in this manner are the (∈, ∈ ∨q)-fuzzy bi-ideals and -fuzzy bi-ideals, which are extension of the concept of a fuzzy bi-ideal in semigroup.     

Tensor and border rank of certain classes of matrices and the fast evaluation of determinant inverse matrix and eigenvalues

The tensor rankA of the linear spaceA generated by the set of linearly independent matricesA ₁, A₂, …, A_p, is the least integert for wich there existt diadsu ^(r) v ^(r)τ, τ=1,2,...,t, such that . IfA=n+k,k≪n then some computational problems concerning matricesA∈A can be solyed fast. For example the parallel inversion of almost any nonsingular matrixA∈A costs 3 logn+0(log² k) steps with max(n ²+p (n+k), k² n+nk) processors, the evaluation of the determinant ofA can be performed by a parallel algorithm in logp+logn+0 (log² k) parallel steps and by a sequential algorithm inn(1+k ²)+p (n+k)+0 (k ³) multiplications. Analogous results hold to accomplish one step of bisection method, Newton's iterations method and shifted inverse power method applied toA−λB in order to compute the (generalized) eigenvalues provided thatA, B∈A. The same results hold if tensor rank is replaced by border rank. Applications to the case of banded Toeplitz matrices are shown. Dedicated to Professor S. Faedo on his 70th birthday Part of the results of this paper has been presented at the Oberwolfach Conference on Komplexitatstheorie, November 1983     

On the complexity of binary samples

Consider a class of binary functions h: X→{ − 1, + 1} on an interval . Define the sample width of h on a finite subset (a sample) S ⊂ X as ω _S (h) =  min _x ∈ S |ω _h (x)| where ω _h (x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function (or trace) of the class , β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples of cardinality m. The estimate is .