A note on the proof of the complexity of the little-preemptive open-shop problem

We give a complement note on the proof of the NP-hardness of preemptive acyclic open-shop problem presented earlier by the authors in Ann. Oper. Res. 159:183–213, 2008.     

Proof complexity of propositional default logic

Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen??s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti??s enhanced calculus for skeptical default reasoning.     

A note on Kolmogorov complexity and entropy

It is shown that the Kolmogorov complexity per symbol of an n-sequence from a stationary ergodic source of finite alphabet approaches the entropy rate of the source in probability as n becomes large.     

Combinatorics of first order structures and propositional proof systems

We define the notion of a combinatorics of a first order structure, and a relation of covering between first order structures and propositional proof systems. Namely, a first order structure M combinatorially satisfies an L-sentence iff holds in all L-structures definable in M. The combinatorics Comb(M) of M is the set of all sentences combinatorially satisfied in M. Structure M covers a propositional proof system P iff M combinatorially satisfies all for which the associated sequence of propositional formulas _n, encoding that holds in L-structures of size n, have polynomial size P-proofs. That is, Comb(M) contains all feasibly verifiable in P. Finding M that covers P but does not combinatorially satisfy thus gives a super polynomial lower bound for the size of P-proofs of _n. We show that any proof system admits a class of structures covering it; these structures are expansions of models of bounded arithmetic. We also give, using structures covering proof systems R^*(log) and PC, new lower bounds for these systems that are not apparently amenable to other known methods. We define new type of propositional proof systems based on a combinatorics of (a class of) structures.Partially supported by grant # A 101 99 01 of the Academy of Sciences of the Czech Republic and by project LN00A056 of The Ministry of Education of the Czech Republic.Also member of the Institute for Theoretical Computer Science of the Charles University. A part of this work was done while visiting the Mathematical Institute, Oxford.     

A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.     

A note on the complexity of minimum dominating set

The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Ω(2ⁿ) algorithm which enumerates and checks all the subsets of nodes. In this paper we present a simple algorithm which solves this problem in O(1.81ⁿ) time.     

A note on the complexity of finding regular subgraphs

Given a graph G and an integer r, does there exist a regular subgraph of G with degree r? In this note we establish NP-completeness for the r-regular subgraph problem for each r ? 3 and certain restrictions on G. In particular, the cubic subgraph problem is NP-complete even for the simple case where G is a bipartite planar graph with maximum degree 4.     

The proof complexity of linear algebra

We introduce three formal theories of increasing strength for linear algebra in order to study the complexity of the concepts needed to prove the basic theorems of the subject. We give what is apparently the first feasible proofs of the Cayley–Hamilton theorem and other properties of the determinant, and study the propositional proof complexity of matrix identities such as AB=I→BA=I.     

关于一个Sobolev不等式的一点注记

讨论了一个与散度为零算子有关的Sobolev不等式,改进和推广了以前的结果.     

A note on some chain conditions

We answer a question raised by Othman Echi: Is an E ₁ (resp., a C ₁) ring an E (resp., a C) ring? We construct a C ₁ (thus E ₁) ring which is not an E ₂ (thus not a C ₂) ring. Received: 11 June 2007     

A semantical proof of the strong normalization theorem for full propositional classical natural deduction

We give in this paper a short semantical proof of the strong normalization for full propositional classical natural deduction. This proof is an adaptation of reducibility candidates introduced by J.-Y. Girard and simplified to the classical case by M. Parigot.     

A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

A simple proof of some ergodic theorems

Some ideas of T. Kamae’s proof using nonstandard analysis are employed to give a simple proof of Birkhoff’s theorem in a classical setting as well as Kingman’s subadditive ergodic theorem.     

A note to the linearity proof of Lorentz transformation

The traditional proof of the linearity of Lorentz transformation makes use of a definition of simultaneity and a physical law for the propagation of light. For unravelling these two elements we use a reverse axiomatic approach to special relativity. In this case we are free, in principle, to introduce an arbitrary simultaneity. Linear coordinate transformations require a linear synchronisation. Lorentz transformation results from a special kind of linear synchronisation.     

A Ramsey-type problem on right-angled triangles in space

It is proved that for any 3-coloring of R³ and for any right-angled triangle T, one can find a congruent copy of T, all of whose vertices are of the same color.     

A note on the representation of quantified statements in terms of the implication operation

We first review Zadeh's theory for representing and reasoning with quantified statements of the formQ A's are B. We then suggest an equivalent representation in terms ofQ X's are (A B). We briefly look at some implications of this new representation.