P-uniform circuit complexity

ABSTRACT

Much complexity-theoretic work on parallelism has focused on the class NC, which is defined in terms of logspace-uniform circuits. Yet P-uniform circuit complexity is in some ways a more natural setting for studying feasible parallelism. In this paper, P-uniform NC (PUNC) is characterized in terms of space-bounded AuxPDAs and alternating Turing Machines with bounded access to the input. The notions of general-purpose and special-purpose computation are considered, and a general-purpose parallel computer for PUNC is presented. It is also shown that NC = PUNC if all tally languages in P are in NC; this implies that the NC = PUNC question and the NC = P question are both instances of the ASPACE(S(n)) = ASPACE,TIME(S(n), S(n)o(1)) question. As a corollary, it follows that NC = PUNC implies PSPACE = DTIME(2no(1)).

REFERENCES

• 1: AHO, A. V., 1-1OPCROFT, J. L., AND ULLMAN, J. L). lime ano tape complexity ot F,usnoown automaton languages. Inf. Control 13 (1968), 186-206.
• 2: ALLENDER, E. W. Invertible functions. Doctoral dissertation. Georgia Institute of Technology, Atlanta, GA, 1985.
• 3: E Allender, The complexity of sparse sets in P, Proc. of the conference on Structure in complexity theory, p.1-11, June 1986, Berkeley, California, United States
• 4: E W Allender, Characterizations of PUNC and precomputation, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.1-10, September 1986, Rennes, France
• 5: Eric W. Allender, Isomorphisms and 1-L reductions, Journal of Computer and System Sciences, v.36 n.3, p.336-350, June 1988 [doi>10.1016/0022-0000(88)90033-5]
• 6: Eric W. Allender , Roy S. Rubinstein, P-printable sets, SIAM Journal on Computing, v.17 n.6, p.1193-1202, Dec. 1988 [doi>10.1137/0217075]
• 7: BALC,~ZAR, J. L., DiAZ, J., AND GABARRO, J. On some "non-uniform" complexity measures. In Proceedings of the 5th Conference on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 199, pp. 18-27.
• 8: Paul W Beame , Stephen A Cook , H James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing, v.15 n.4, p.994-1003, Nov. 1986 [doi>10.1137/0215070]
• 9: BooK, R.V. Tally languages and complexity classes. Inf. Control 26, (1974), 186-193.
• 10: BORODIN, A. On relating time and space to size and depth. SlAM J. Comput. 6 (1977), 733-744.
• 11: Franz-Josef Brandenburg, On one-way auxiliary pushdown automata, Proceedings of the 3rd GI-Conference on Theoretical Computer Science, p.132-144, March 28-30, 1977
• 12: Franz-Josef Brandenburg, The Contextsensitivity Bounds of Contextsensitive Grammars and Languages, Proceedings of the Fourth Colloquium on Automata, Languages and Programming, p.120-134, July 18-22, 1977
• 13: S. R. Buss, The Boolean formula value problem is in ALOGTIME, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.123-131, January 1987, New York, New York, United States [doi>10.1145/28395.28409]
• 14: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 15: CHANDRA, A. K., STOCKMEVER, L. J., AND VISHKIN, U. Constant depth reducibiilty. SIAM J. Comput. !3 (!984), 423-439.
• 16: Jik H. Chang , Oscar H. Ibarra , Bala Ravikumar , Leonard Berman, Some observations concerning alternating Turing machines using small space, Information Processing Letters, v.25 n.1, p.1-9, 20 April 1987 [doi>10.1016/0020-0190(87)90085-8]
• 17: CHVTIL, M.P. Comparison of the active visiting and the crossing complexities. In Proceedings of the 6th Conference on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 53. Springer-Verlag, New York, 1977, pp. 272-281.
• 18: Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
• 19: COOK, S.A. Towards a complexity theory of synchronous parallel computation. L'Enseignement Math. 27 (1981), 99-124.
• 20: Stephen A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Control, v.64 n.1-3, p.2-22, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80041-3]
• 21: Patrick William Dymond, Simultaneous resource bounds and parallel computation, 1980
• 22: Patrick W. Dymond , Stephen A. Cook, Complexity theory of parallel time and hardware, Information and Computation, v.80 n.3, p.205-226, Mar. 1989 [doi>10.1016/0890-5401(89)90009-6]
• 23: GALIL, Z. Some thoryu of computation as qucations about two-way deterministic pushdown automaton languages. Math. Syst. Theory 10 (1977), 211-228.
• 24: Zvi Galil , Wolfgang J. Paul, An Efficient General-Purpose Parallel Computer, Journal of the ACM (JACM), v.30 n.2, p.360-387, April 1983 [doi>10.1145/322374.322382]
• 25: Leslie M. Goldschlager, A universal interconnection pattern for parallel computers, Journal of the ACM (JACM), v.29 n.4, p.1073-1086, Oct. 1982 [doi>10.1145/322344.322353]
• 26: HARTMANIS, J., AND MAHANEY, S. Languages simultaneously complete for one-way and two-way log-tape automata. SlAM J. Comput. 10 (1981), 383-390.
• 27: HARTMANIS, J., AND YESHA, Y. Computation times of NP sets of different densities. Theoret. Comput. Sci. 34 (1984), 17-32.
• 28: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 29: HUYNH, D.T. Non-uniform complexity and the randomness of certain complete languages. Tech. Rep. TR 85-34. Computer Science Department, Iowa State Univ., Ames, IA, 1985.
• 30: ITO, A., INOUE, K., AND TAKANAMI, I. A note on alternating Turing machines using small space. Trans. 1EICE (Japan), Section E, 70 (1987), 990-996.
• 31: JONES, N.D. Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11 (1975), 68-85.
• 32: K. N. King, Measures of parallelism in alternating computation trees (Extended Abstract), Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.189-201, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802472]
• 33: K. N. King, Alternating Multihead Finite Automata (Extended Abstract), Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.506-520, July 13-17, 1981
• 34: MAGER, G. Writing pushdown acceptors. J. Comput. Syst. Sci. 3 (1986), 276-319.
• 35: MAHANEY, S.R. Sparse sets and reducibilities, in Studies in Complexity Theory, R. V. Book, Ed. Wiley, New York, 1986.
• 36: Mix BARRINGTON, D. A., IMMERMAN, N., AND STRAUBING, H. On uniformity within NC*. In Proceedings of the 3rd Structure in Complexity Theory Conference. IEEE Computer Society Press, Washington, D.C., 1988, pp. 47-59.
• 37: PIPPENGER, N. On simultaneous resource bounds. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1979, pp. 307-311.
• 38: REir, J. On threshold circuits and polynomial computation. In Proceedings of the 2nd Structure in Complexity Theory Conference. 1987, pp. 118-123.
• 39: Ruzzo, W.L. Tree-size bounded alternation. J. Comput. Syst. Sci. 21 (1980),218-235.
• 40: Ruzzo, W.L. On uniform circuit complexity. J. Comput. Syst. Sci. 21 (1981), 365-383.
• 41: STOCKMEYER, L.J. The complexity of decision problems in automata theory and logic. Doctoral dissertation. Massachusetts Inst. of Technology, Cambridge, Mass., 1974.
• 42: SUDBOROUGH, I.H. Bandwidth constraints on problems complete for polynomial time. Theoret. Comput. Sci. 26 (1983), 25-52.
• 43: VON ZUR GATHEN, J. Parallel powering. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing. ACM, New York, I984, pp. 31-36.
• 44: VISHKIN, U. Synchronous Parallel ComputationmA Survey. Tech. Rep. TR 71. Department of Computer Science, Courant Inst., New York Univ., New York, 1983.
• 45: Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]
• 46: WECHSUNG, G. The oscillation complexity and a hierarchy of context-free languages. In Proceedings of the 2nd International Conference on Fundamentals of Computation Theory. Akademie-Verlag, Berlin, GDR, 1979, pp. 508-515.
• 47: WECHSUNG, G. A note on return complexity. Elektronische Informationsverarbeitung und Kybernetik 16 (1980), 139-146.
• 48: WECHSUNG, G., AND BRANDSTADT, m. A relation between space, return and dual return complexities. Theoret. Comput. Sci. 9 (1979), 127-140.
• 49: WILSON, C. B. On the decomposability of NC and AC. In Proceedings of the 4t,~ Structure in Complexity Theory Conference. IEEE Computer Society Press, Washington, D.C., 1989, pp. 124-131.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Languages, Theory, Verification