文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > The Hebrew University
侵权投诉

The Hebrew University

We prove that monotone circuits computing the perfect matching function on n-vertex graphs require\Omega\Gamma n) depth. This implies an exponential gap between the depth of monotone and nonmonotone circuits.

Monotone Circuits for Matching Require Linear Depth Ran Raz Avi Wigderson The Hebrew University We prove that monotone circuits computing the perfect matching function on n-vertex graphs require (n) depth. This implies an exponential gap between the depth of monotone and nonmonotone circuits.

Abstract

CR categories: F.1.1, Models of Computation, Unbounded Action Devices. General Terms: THEORY Key words: circuit depth, monotone computation, perfect matching

In 1985 Razborov R1] proved a superpolynomial lower bound on the size of monotone circuits computing the perfect matching function. As matching is in P, this result rst showed a superpolynomial gap between the size of monotone and non-monotone circuits. This gap was shown to be exponential by Tardos T] (with a di erent monotone function in P ). Another exponential gap for size, when the circuits are restricted to have constant depth, was proved by Ajtai and Gurevich AG]. Karchmer and Wigderson KW] studied the depth of boolean circuits, and characterized it in communication complexity terms. This approach was This research was partially supported by the American-Israeli Binational Science Foundation grant number 87-00082

1 Introduction

第1页

你可能喜欢

热门文档

相关文档

  • The Hebrew University Jerusalem

    Beeri: School of Computer Science and Engineering, The Hebrew University, Jerusalem 91904, Israel, beeri@cs.huji.ac.il. Permission to make digital/hard ...

  • The Hebrew University Jerusalem

    Beeri: School of Computer Science and Engineering, The Hebrew University, Jerusalem 91904, Israel, beeri@cs.huji.ac.il. Permission to make digital/hard ...

  • Hebrew University

    Hebrew University 29页 免费 The Hebrew University ... 暂无评价 53页 免费 Kalai (Hebrew Universi... 78页 免费 Hebrew University 暂无评价 12页 免费 喜欢...

  • Hebrew University

    Hebrew University and 19页 免费 The Hebrew University 37页 免费 Hebrew University Shmuel... 暂无评价 20页 免费 The Hebrew University of... 153页 免费 ...

  • Hebrew University

    Hebrew University and 19页 免费 The Hebrew University 37页 免费 Hebrew University Shmuel... 暂无评价 20页 免费 The Hebrew University of... 153页 免费 ...

  • Hebrew University, Jerusalem,

    The Hebrew University of... 153页 免费 The Hebrew University Je... 暂无评价 53页 免费 The Hebrew University Je... 暂无评价 53页 免费 Hebrew Universi...

  • Hebrew University

    Hebrew University and 19页 免费 The Hebrew University 37页 免费 Hebrew University Shmuel... 暂无评价 20页 免费 The Hebrew University of... 153页 免费 ...

  • Hebrew University

    Hebrew University Shmu... 暂无评价 20页 免费 The Hebrew University ... 153页 免费 Hebrew University, Jer... 20页 免费 The Hebrew University ... 暂无...

  • Hebrew University Shmuel Safra

    47页 免费 Shmuel Safra z 暂无评价 9页 免费 Hebrew University and 19页 免费 The Hebrew University 37页 免费 by Shmuel Safra 暂无评价 49页 免费搜...

  • 亚洲名校——以色列耶路撒冷希伯来大学

    希伯来大学全称为耶路撒冷希伯来大学 (The Hebrew University of Jerusalem)是以色列最著名的高等学府,也是世界上首屈一指的综合性大学之一。 1918年,犹太复国运动领袖...

  • 2012-世界大学排名新鲜出炉 Academic Ranking of World...

    University - University Park Vanderbilt University Carnegie Mellon University The University of Edinburgh Technical University Munich The Hebrew University of 34 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email