Linear comparison complexity of the n-cube membership problem

1. E. Györi, An n-dimensional search problem with restricted questions. Combinatorica 1(4) (1981) 377–380.

   Google Scholar 

2. J. Morávek, On the complexity of discrete programming problems. (talk) 6th International Symposium on Math. Programming, Princeton University 1967.

   Google Scholar 

3. J. Morávek, Über die algorithmische Komplexität des Problems der diskreten Optimierung. 12. Int. Kolloquium, TH Ilmenau, DDR, 1967.

   Google Scholar 

4. J. Morávek, On the complexity of disrete programming problems. Aplikace matematiky 14, 1969, 442–474.

   Google Scholar 

5. J. Morávek, A localization problem in geometry and complexity of discrete programming. Kybernetika (Prague) 8: 498–516 (1972).

   Google Scholar 

6. J. Morávek, A geometrical method in combinatorial complexity. Aplikace matematiky 26: 82–96 (1981).

   Google Scholar 

7. J. Morávek, Decision trees and lower bound for complexity of linear programming, in Graphs and Other Combinatorial Topics. M. Fiedler, Ed., Proc. of the Third Czechoslovak Symposium on Graph Theory, held in Prague, 1982.

   Google Scholar 

8. J. Morávek, P. Pudlák, New lower bound for polyhedral membership problem with an application to linear programming. Lecture Notes in Computer Science, Vol. 176, Proceedings of MFCS 1984, pp. 416–424, Springer-Verlag 1984.

   Google Scholar 

9. J.W. Jaromczyk, Linear decision trees are too weak for convex hull problem. Infor. Process. Lett. 12 (1981), No.3, 138–141.

   Google Scholar 

10. H. Machida, A lower bound on the complexity of knapsack problem. Proceedings of the Seventh I.B.M. Symposium on Mathematical Foundation of Computer Science (1982), 1–23.

    Google Scholar 

11. H. Nakayama, T. Nishizeki and N. Saito, Lower bounds for some graph-problems. Journal of Algorithms, to appear.

    Google Scholar 

12. I. Pohl, A sorting problem and its complexity, Comm of the ACM 15(1972), 462–464.

    Google Scholar 

13. S.S. Kislicyn, O vydělenii k-go elementa uporjadočennoj sovokupnosti putěm poparnych sravněnij. Sibirskij mat. žurnal (Siberian Math. Journal), 5, 1964, 557–564.

    Google Scholar 

Download references