A linear time parallel algorithm for the 2-CNF satisfiability problem

机译：2-CNF可满足性问题的线性时间并行算法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

This paper presents a parallel algorithm for finding a satisfying truth assignment to a given 2-CNF-SAT problem on a tree machine model of computation. The algorithm requires O(log_2 n) complexity time using a tree machine model of computation with n leaf processing elements.

机译：本文提出了一种并行算法，用于在树型计算机模型上找到给定的2-CNF-SAT问题的令人满意的真值分配。使用具有n个叶处理元素的树型计算机模型，该算法需要O（log_2 n）复杂度时间。

著录项

来源
《International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'2001) Vol.2, Jun 25-28, 2001, Las Vegas, Nevada, USA》|2001年|p.761-765|共5页
会议地点 Las Vegas NV(US);Las Vegas NV(US)
作者
El-Sayed M. El-Horbaty;
展开▼
作者单位

Dept. Of Computer Science, Faculty of Computer Information Sciences, Ain Shams University, EGYPT;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类自动化技术、计算机技术;
关键词
2-CNF-SAT; parallel algorithms; tree machines; complexity time;

机译：2-CNF-SAT;并行算法；树机；复杂度时间;

相似文献

外文文献
中文文献
专利

1. Planning as satisfiability: parallel plans and algorithms for plan search [J] . Rintanen J, Hejanko K, Niemela I Artificial intelligence . 2006,第12a13期

机译：作为可满足性的计划：用于计划搜索的并行计划和算法
2. Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random satisfiability problem, and its application to stop-and-restart resolutions - art. no. 037101 [J] . Cocco S., Monasson R. Physical review, E. Statistical physics, plasmas, fluids, and related interdisciplinary topics . 2002,第3aPta2b期

机译：指数难度的问题有时是多项式，针对随机可满足性问题的搜索算法的大偏差分析及其在停止和重新启动分辨率中的应用-艺术。没有。 037101
3. Parallel in Time Algorithms for Nonlinear Iterative Methods [J] . Mustafa Gaja, Olga Gorynina ESAIM: Proceedings and Surveys . 2018,第1期

机译：非线性迭代方法的并行时间算法
4. A linear time parallel algorithm for the 2-CNF satisfiability problem [C] . El-Sayed M. El-Horbaty International conference on parallel and distribute processing techniques and applications . 2001

机译：用于2-CNF可靠性问题的线性时间并行算法
5. Parallel algorithms and software for time-dependent systems of nonlinear partial differential equations with an application in computational biology. [D] . Murillo, Maria Silva. 2002

机译：非线性偏微分方程时间相关系统的并行算法和软件及其在计算生物学中的应用。
6. Phase transitions of the typical algorithmic complexity of the random satisfiability problem studied with linear programming [O] . Hendrik Schawe, Roman Bleim, Alexander K. Hartmann 2012

机译：线性规划研究随机可满足性问题的典型算法复杂度的相变
7. Linear-time algorithms for testing the satisfiability of propositional horn formulae [O] . Dowling William F., Gallier Jean H. 1984

机译：用于测试命题号角公式可满足性的线性时间算法
8. Efficient Algorithms for Certain Satisfiability and Linear Programming Problems [R] . Aspvall, B. I. 1980

机译：某些可满足性和线性规划问题的有效算法

A linear time parallel algorithm for the 2-CNF satisfiability problem

摘要

著录项

相似文献

相关主题

期刊订阅