A counterexample to a conjecture of McDanell

A partially singular optimal control trajectory will contain one or more junctions at which nonsingular and singular subarcs are joined. McDanell's conjecture concerns the necessary conditions for optimality at such a junction. The conjecture is divided into two parts, each part distinguished by the relative magnitudes of two parameters. Until now the conjecture has been proved correct for several different classes of problem. However, this paper presents a partially singular optimal control trajectory containing one junction for which one part of the conjecture is untrue. Attempts to construct a similar trajectory in order to disprove the second part of the conjecture have so far been unsuccessful.     

A counterexample to Mustafa-Glovers'' monotonicity conjecture

It is conjectured by Mustafa and Glover (1990) that the norm of the closed-loop transfer function monotonically increases as the specified norm bound y increases, if the so-called central controller is used. In this paper, a simple counterexample is given by reducing the problem to an interpolation problem. A sufficient condition which guarantees the monotonicity of the γ-characteristic is shown.     

A counterexample to a conjecture concerning concatenation hierarchies

We give a counterexample to the conjecture which was originally formulated by Straubing in 1986 concerning a certain algebraic characterization of regular languages of level 2 in the Straubing-Thérien concatenation hierarchy of star-free languages.     

A counterexample to an algorithm for computing monotone hulls of simple polygons

A two-stage algorithm was recently proposed by Sklansky (1982) for computing the convex hull of a simple polygon P. The first step is intended to compute a simple polygon $\text{P}{}^1$ which is monotonic in both the x and y directions and which contains the convex hull vertices of P. The second step applies a very simple convex hull algorithm on $\text{P}{}^1$. In this note we show that the first step does not always work correctly and can even yield non-simple polygons, invalidating the use of the second step. It is also shown that the first step can discard convex hull vertices thus invalidating the use of any convex hull algorithm in the second step.     

A counterexample for the proof of implication conjecture on independent spanning trees

Khuller and Schieber (1992) in [1] developed a constructive algorithm to prove that the existence of k-vertex independent trees in a k-vertex connected graph implies the existence of k-edge independent trees in a k-edge connected graph. In this paper, we show a counterexample where their algorithm fails.     

Numerical solutions to the Witsenhausen counterexample byapproximating networks

Approximate solutions to the Witsenhausen counterexample (1968) are derived by constraining the unknown control functions to take on fixed structures containing “free” parameters to be optimized. Such structures are given by “nonlinear approximating networks”, i.e., linear combinations of parametrized basis functions that benefit by density properties in normed linear spaces. This reduces the original functional problem to a nonlinear programming one which is solved via stochastic approximation. The method yields lower values of the costs than the ones achieved so far in the literature, and, most of all, provides rather a complete overview of the shapes of the optimal control functions when the two parameters that characterize the Witsenhausen counterexample vary. One-hidden-layer neural networks are chosen as approximating networks     

A counterexample to a diameter algorithm for convex polygons

Recently, Snyder and Tang [1] proposed an algorithm for finding the diameter of a convex polygon. In this note a family of convex polygons is described for which their algorithm fails. It is also pointed out that the diameter of an arbitrary simple n-vertex polygon can be computed in O(n) time.     

A counterexample to the Alexopoulos-Griffin path planning algorithm

The planar stationary-obstacle path-planning problem for polygonal obstacles has been correctly and completely solved by T. Lozano-Perez and M. Wesley (1979), i.e., a global, optimal algorithm was provided which requires O(mu(2)logmu) computation time, where mu is the number of obstacle-faces in the scene. That algorithm is known as the VGRAPH algorithm. Two variants of VGRAPH have been developed to solve the same problem in O(mu(2)) computation time. Our paper discusses a recent algorithm proposed by C. Alexopoulos and P.M. Griffin (1992), called V*GRAPH, which also claims to provide an optimal solution. We demonstrate by counter-example that V*GRAPH is neither global nor optimal.     

Complexity of monotone networks for Boolean matrix product

Any computation of Boolean matrix product by an acyclic network using only the operations of binary conjunction and disjunction requires at least IJK conjunctions and IJ(K?1) disjunctions for the product of matrices of sizes I×K and K×J. Furthermore any two such networks having these minimum numbers of operations are equivalent using only the commutativity of both operations and the associativity of disjunction.     

A counterexample to the chain rule for conditional HILL entropy

Most entropy notions \({H(.)}\) like Shannon or min-entropy satisfy a chain rule stating that for random variables \({X,Z,}\) and \({A}\) we have \({H(X|Z,A)\ge H(X|Z)-|A|}\). That is, by conditioning on \({A}\) the entropy of \({X}\) can decrease by at most the bitlength \({|A|}\) of \({A}\). Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions \({(X,Z,A)}\), where \({A}\) is a distribution over a single bit, such that the HILL entropy H ^HILL \({(X|Z)}\) is large but H ^HILL \({(X|Z,A)}\) is basically zero.Our counterexample just makes the minimal assumption that \({{\mathbf{NP}} \nsubseteq{\mathbf{P/poly}}}\). Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable.Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object.     

A note on a system theoretic approach to a conjecture by Peller-Khrushchev

Based on the construction of infinite dimensional balanced realizations an alternative solution to the following inverse spectral problem is presented: Given a monotonically decreasing sequence of positive numbers (σ_n)_{n 1}, does there exist a Hankel operator whose sequence of singular values is (σ_n)_{n 1}?     

一种参照模糊集的云模型集合论方法研究

参照模糊集构建云模型的集合论方法能够很好地扩展云模型的应用领域。本文提出了一种参照模糊集的云模型集合论方法。对云模型及其组成元素进行了阐述,提出了云集合元素的I运算和P运算,在此基础上给出了云集合的基础运算方法,研究了云集合的截集和分解定理。本文研究对云模型在集合理论方面的拓展具有较好的参考意义。     

Convergence of semidiscrete approximations to optimal control problems in hilbert spaces: A counterexample

In this paper we give and discuss a counterexample related to the approximation of non-quadratic optimal control problems for linear distributed parameter systems. More precisely, we show that the assumption (1.7), which has been proved in a previous paper to be sufficient, is also necessary for the convergence (at least in the most general setting of the problem).     

基于椭圆曲线的Schnorr门限签名方案

提出了一种基于椭圆曲线密码体制(ECC)的Schnorr型(t, n)门限数字签名方案,并对该方案的安全性进行了分析.方案由系统初始化、子密钥产生过程、签名过程和签名验证四个部分组成.方案除了在子密钥产生阶段需要保密通信外,在签名阶段不需要安全的通信信道.基于椭圆曲线密码体制和Schnorr密码体制保证了方案的安全性.     

ALOGTIME and a conjecture of S.A. Cook

Usingsequential, machine-independent characterization of theparallel complexity classesAC ^k andNC ^k , we establish the following conjecture of S.A. Cook. There is a free variable equational logicALV with the property thatif f, g are function symbols forALOGTIME computable functions for which f=g is provable inALV, then there are polynomial size Frege proofs for the infinite family {|f=g| _m ⁿ :n, m} of propositional tautologies. Here, the propositional formula |f=g| _m ⁿ expresses the equality off andg on inputs of length at mostn, provided that the function values are of length at mostm. We establish a related result with constant formula-depth polynomial size Frege proofs for a systemAV related to uniformAC ⁰ functions.Part of this research supported by NSF Grant # DCR-860615. Extended abstract of this paper appeared in theIEEE Proc. of Logic in Computer Science, Philadelphia (June 1990).