咨询与建议

限定检索结果

文献类型

  • 5 篇 期刊文献
  • 4 篇 会议

馆藏范围

  • 9 篇 电子文献
  • 0 种 纸本馆藏

日期分布

学科分类号

  • 6 篇 理学
    • 6 篇 数学
    • 2 篇 物理学
  • 6 篇 工学
    • 6 篇 计算机科学与技术...
    • 2 篇 软件工程

主题

  • 9 篇 satisfiability a...
  • 2 篇 satisfiability p...
  • 2 篇 circuit complexi...
  • 1 篇 linear threshold...
  • 1 篇 quantified boole...
  • 1 篇 random restricti...
  • 1 篇 motion planning
  • 1 篇 error correcting...
  • 1 篇 pseudorandom gen...
  • 1 篇 proof complexity
  • 1 篇 autonomous mobil...
  • 1 篇 uniformity
  • 1 篇 pspace-complete
  • 1 篇 obdd
  • 1 篇 comparator circu...
  • 1 篇 np-complete
  • 1 篇 robot swarm
  • 1 篇 threshold circui...
  • 1 篇 average-case com...
  • 1 篇 average case low...

机构

  • 2 篇 ural fed univ de...
  • 2 篇 univ edinburgh s...
  • 1 篇 sanchez comp ass...
  • 1 篇 russian acad sci...
  • 1 篇 univ pisa dept c...
  • 1 篇 univ oxford dept...
  • 1 篇 mit elect engn &...
  • 1 篇 univ montpellier...
  • 1 篇 stanford univ de...
  • 1 篇 indian inst sci ...
  • 1 篇 carnegie mellon ...
  • 1 篇 univ warwick dep...
  • 1 篇 univ calif san d...

作者

  • 2 篇 gorbenko anna
  • 2 篇 santhanam rahul
  • 2 篇 popov vladimir
  • 1 篇 hooker jn
  • 1 篇 williams ryan
  • 1 篇 itsykson dmitry
  • 1 篇 rago g
  • 1 篇 williams r. ryan
  • 1 篇 lu zhenjian
  • 1 篇 knop alexander
  • 1 篇 romashchenko and...
  • 1 篇 shrivastava a
  • 1 篇 paturi ramamohan
  • 1 篇 chandru v
  • 1 篇 sokolov dmitry
  • 1 篇 schneider stefan
  • 1 篇 impagliazzo russ...
  • 1 篇 cavalar bruno p.

语言

  • 9 篇 英文
检索条件"主题词=Satisfiability algorithms"
9 条 记 录,以下是1-10 订阅
排序:
Fighting Perebor: New and Improved algorithms for Formula and QBF satisfiability
Fighting Perebor: New and Improved Algorithms for Formula an...
收藏 引用
IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)
作者: Santhanam, Rahul Univ Edinburgh Sch Informat Edinburgh Midlothian Scotland
We investigate the possibility of finding satisfying assignments to Boolean formulae and testing validity of quantified Boolean formulae (QBF) asymptotically faster than a brute force search. Our first main result is ... 详细信息
来源: 评论
A satisfiability Algorithm for Sparse Depth Two Threshold Circuits
A Satisfiability Algorithm for Sparse Depth Two Threshold Ci...
收藏 引用
IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS)
作者: Impagliazzo, Russell Paturi, Ramamohan Schneider, Stefan Univ Calif San Diego La Jolla CA 92093 USA
We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interes... 详细信息
来源: 评论
algorithms and Lower Bounds for Comparator Circuits from Shrinkage
收藏 引用
ALGORITHMICA 2023年 第7期85卷 2131-2155页
作者: Cavalar, Bruno P. Lu, Zhenjian Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Oxford Dept Comp Sci Oxford England
In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restricti... 详细信息
来源: 评论
Partial instantiation methods for inference in first-order logic
收藏 引用
JOURNAL OF AUTOMATED REASONING 2002年 第4期28卷 371-396页
作者: Hooker, JN Rago, G Chandru, V Shrivastava, A Carnegie Mellon Univ Grad Sch Ind Adm Pittsburgh PA 15213 USA Univ Pisa Dept Comp Sci I-56125 Pisa Italy Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Sanchez Comp Associates Bangalore 560003 Karnataka India
satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a ... 详细信息
来源: 评论
On Uniformity and Circuit Lower Bounds
收藏 引用
COMPUTATIONAL COMPLEXITY 2014年 第2期23卷 177-205页
作者: Santhanam, Rahul Williams, Ryan Univ Edinburgh Sch Informat Edinburgh Midlothian Scotland Stanford Univ Dept Comp Sci Stanford CA 94305 USA
We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts: 1. Lower bounds against medium-uniform circ... 详细信息
来源: 评论
ON OBDD-BASED algorithms AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
收藏 引用
JOURNAL OF SYMBOLIC LOGIC 2020年 第2期85卷 632-670页
作者: Itsykson, Dmitry Knop, Alexander Romashchenko, Andrei Sokolov, Dmitry Russian Acad Sci VA Steklov Math Inst St Petersburg Dept St Petersburg Russia Univ Montpellier CNRS LIRMM Montpellier France
In 2004 Atserias, Kolaitis, and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false OBDD from OBDDs representing clauses of the initi... 详细信息
来源: 评论
The Discrete Minimum Constraint Removal Motion Planning Problem
The Discrete Minimum Constraint Removal Motion Planning Prob...
收藏 引用
International Conference on Numerical Analysis and Applied Mathematics (ICNAAM)
作者: Gorbenko, Anna Popov, Vladimir Ural Fed Univ Dept Intelligent Syst & Robot Math & Comp Sci Inst Ekaterinburg 620083 Russia
Many planning problems for robots are of considerable interest. In this paper, we consider the discrete minimum constraint removal motion planning problem that can be used for a motion planning formulation with explan... 详细信息
来源: 评论
The Problem of Robot Swarms Control with only Global Signals
The Problem of Robot Swarms Control with only Global Signals
收藏 引用
International Conference on Numerical Analysis and Applied Mathematics (ICNAAM)
作者: Gorbenko, Anna Popov, Vladimir Ural Fed Univ Dept Intelligent Syst & Robot Math & Comp Sci Inst Ekaterinburg 620083 Russia
Problems of swarm robotics are extensively studied in contemporary robotics. In this paper, we consider the problem of robot swarms control with only global signals. We propose an efficient approach to solve the probl... 详细信息
来源: 评论
New algorithms and Lower Bounds for Circuits With Linear Threshold Gates
收藏 引用
THEORY OF COMPUTING 2018年 14卷
作者: Williams, R. Ryan MIT Elect Engn & Comp Sci 77 Massachusetts Ave Cambridge MA 02139 USA
Let ACC circle THR be the class of constant-depth circuits comprised of AND, OR, and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary linear threshold functions. This class of ... 详细信息
来源: 评论