变元正负出现概率受控的随机正则k-SAT问题研究

结题报告
项目介绍
AI项目解读

基本信息

  • 批准号：
    61862051
  • 项目类别：
    地区科学基金项目
  • 资助金额：
    37.0万
  • 负责人：
    周锦程
  • 依托单位：
    黔南民族师范学院
  • 学科分类：
    F0201.计算机科学的基础理论
  • 结题年份：
    2022
  • 批准年份：
    2018
  • 项目状态：
    已结题
  • 起止时间：
    2019-01-01 至2022-12-31

项目摘要

The regular random (k,r)-SAT problem is a special k-SAT problem obtained by restricting the k-CNF instances where each variable occurs precisely r times and both the probabilities of the variable’s positive and negative occurrences are 1/2. It is worth to study theoretically because it is much more difficult to solve than the general random k-SAT problem. In this project, we will study a new random equilibrium k-SAT problem, named regular random p-(k,r)-SAT problem, which is achieved by restricting the k-SAT problem instances where each variable occurs precisely r times and each of the positive variable occurs probability is p, correspondingly, the negative one is 1-p. Therefore, it is more general than the regular random (k,r)-SAT problem... This project will investigate the instances generation model, the easy and the hard subclass distributions, the structure characteristics of hard instances, the phase transition phenomenons and decision algorithms to the regular random (k,r)- SAT problem. It is expected that the research results will help us to further explore the properties of the random equilibrium k-SAT problems and recognize the essential of the NP complete problems. Futhermore, These research results would also help us to detect the general mathematical phenomena and design some more effective decision algorithms for the SAT problem.
随机正则(k,r)-SAT问题是限制每个变元恰好出现r次且其变元正、负出现概率均为1/2的随机k-SAT子问题，因其相变点处的随机正则(k,r)-CNF实例远比同规模相应相变点处的随机k-CNF实例更难判定而极具研究价值。本项目拟研究一种变元正、负出现概率受控且比随机正则(k,r)-SAT问题更为泛化的随机均衡k-SAT问题，即研究每个变元恰好出现r次且其以p的概率正出现、而以1-p的概率负出现的随机正则p-(k,r)-SAT问题。我们将围绕该问题的实例生成模型、易解子类分布情况、解空间的结构特征、可满足相变现象、难解实例特征、难解实例构造、判定算法等方面对其进行深入的研究，以期进一步探索随机均衡k-SAT问题的相关性质，为进一步认识NP完全问题的本质特性、发现SAT问题的一般数学现象和设计更为有效的SAT判定算法奠定基础。

结项摘要

随机正则(k,r)-SAT问题是限制每个变元恰好出现r次且其变元正、负出现概率均为1/2的随机k-SAT子问题，因其相变点处的随机正则(k,r)-CNF实例远比同规模相应相变点处的随机k-CNF实例更难判定而极具研究价值。本项目研究了变元正、负出现概率受控且比随机正则(k,r)-SAT问题更为泛化的随机均衡k-SAT问题，即研究每个变元恰好出现r次且其以p的概率正出现、而以1-p的概率负出现的随机正则p-(k,r)-SAT问题。我们围绕该问题的实例生成模型、易解子类分布情况、解空间的结构特征、可满足相变现象、难解实例特征、难解实例构造、判定算法等方面对其进行了深入的研究，以期进一步为探索随机均衡k-SAT问题的相关性质，为进一步认识NP完全问题的本质特性、发现SAT问题的一般数学现象和设计更为有效的SAT判定算法奠定基础。

项目成果

期刊论文数量（21）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
The Transition Phenomenon of (1,0)-d-Regular (k, s)-SAT
(1,0)-d-Regular (k,s)-SAT的转变现象
  • DOI：
    10.3390/electronics11152475
  • 发表时间：
    2022-08-01
  • 期刊：
    ELECTRONICS
  • 影响因子：
    2.9
  • 作者：
    Fu，Zufeng;Wang，Haiying;Pi，Yihai
  • 通讯作者：
    Pi，Yihai
(1,0)-Super Solutions of (k,s)-CNF Formula.
(k,s)-CNF公式的(1,0)-超解
  • DOI：
    10.3390/e22020253
  • 发表时间：
    2020-02-23
  • 期刊：
    Entropy (Basel, Switzerland)
  • 影响因子：
    --
  • 作者：
    Fu Z;Xu D;Wang Y
  • 通讯作者：
    Wang Y
Comparison and Analysis of Several Clustering Algorithms for Pavement Crack Segmentation Guided by Computational Intelligence.
计算智能引导下路面裂缝分割的几种聚类算法对比分析
  • DOI：
    10.1155/2022/8965842
  • 发表时间：
    2022
  • 期刊：
    Computational intelligence and neuroscience
  • 影响因子：
    --
  • 作者：
  • 通讯作者：
An algorithm for solving satisfiability problem based on the structural information of a formula
一种基于公式结构信息的可满足性问题求解算法
  • DOI：
    10.1007/s11704-021-0318-8
  • 发表时间：
    2021
  • 期刊：
    Frontiers of Computer Science
  • 影响因子：
    4.2
  • 作者：
    张再军;许道云
  • 通讯作者：
    许道云
Deep learning optimization and technoenvironmental analysis of a solar-driven multigeneration system for producing sustainable hydrogen and electricity: A case study of San Francisco
用于生产可持续氢和电力的太阳能驱动多联产系统的深度学习优化和技术环境分析：以旧金山为例
  • DOI：
    10.1016/j.ijhydene.2022.09.301
  • 发表时间：
    --
  • 期刊：
    International Journal of Hydrogen Energ
  • 影响因子：
    --
  • 作者：
    Tao Hai;Jincheng Zhou;Sattam Fahad Almojil;Abdulaziz Ibrahim Almohana;Abdulrhman Fahmi Alali;Sadok Mehrez;Abdullah Mohamed;Kamal Sharma;Azheen Ghafour Mohammed;Khaled Twfiq Almoalimi
  • 通讯作者：
    Khaled Twfiq Almoalimi

数据更新时间：{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--"}}
  • 发表时间：
    {{ item.publish_year || "--" }}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--"}}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ monograph.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者：
    {{ item.authors }}

数据更新时间：{{ patent.updateTime }}

其他文献

On the Satisability Threshold of Regular (k, s)-SAT
论常规(k,s)-SAT的满意度阈值
  • DOI：
    --
  • 发表时间：
    2015
  • 期刊：
    Journal of Computational Information Systems
  • 影响因子：
    --
  • 作者：
    周锦程
  • 通讯作者：
    周锦程
严格随机正则(3,s)-SAT模型及其相变现象
  • DOI：
    10.13700/j.bh.1001-5965.2015.0845
  • 发表时间：
    2016
  • 期刊：
    北京航空航天大学学报
  • 影响因子：
    --
  • 作者：
    周锦程;许道云;卢友军;代寸宽
  • 通讯作者：
    代寸宽
随机正则(k, r)-SAT 问题的可满足临界
  • DOI：
    --
  • 发表时间：
    2016
  • 期刊：
    软件学报
  • 影响因子：
    --
  • 作者：
    周锦程;许道云;卢友军
  • 通讯作者：
    卢友军
On-the-Satisfiability-Threshold-of-Regular-(k,s)-SAT
常规-(k,s)-SAT 的可满足性阈值
  • DOI：
    --
  • 发表时间：
    2015
  • 期刊：
    Journal of Computational Information Systems
  • 影响因子：
    --
  • 作者：
    周锦程;许道云;Youjun Lu
  • 通讯作者：
    Youjun Lu
基于1RSB的正则(k,r)-SAT问题可满足临界
  • DOI：
    10.13245/j.hust.171202
  • 发表时间：
    2017
  • 期刊：
    华中科技大学学报(自然科学版)科技大学
  • 影响因子：
    --
  • 作者：
    周锦程;许道云;卢友军
  • 通讯作者：
    卢友军

其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--" }}
  • 发表时间：
    {{ item.publish_year || "--"}}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--" }}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}
empty
内容获取失败，请点击重试
重试联系客服
title开始分析
查看分析示例
此项目为已结题，我已根据课题信息分析并撰写以下内容，帮您拓宽课题思路：

AI项目思路

AI技术路线图

相似国自然基金

{{ item.name }}
  • 批准号：
    {{ item.ratify_no }}
  • 批准年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}

相似海外基金

{{ item.name }}
{{ item.translate_name }}
  • 批准号：
    {{ item.ratify_no }}
  • 财政年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}
{{ showInfoDetail.title }}

作者：{{ showInfoDetail.author }}

知道了

AI项目解读示例

课题项目：调控A型流感病毒诱导IFN-β表达的机制研究

AI项目摘要：

本研究聚焦于TRIM2蛋白在A型流感病毒诱导的IFN-β表达中的调控机制。A型流感病毒是全球性健康问题，其感染可导致严重的呼吸道疾病。IFN-β作为关键的抗病毒因子，其表达水平对抗病毒防御至关重要。然而，TRIM2如何调控IFN-β的表达尚未明确。本研究假设TRIM2通过与病毒RNA或宿主因子相互作用，影响IFN-β的产生。我们将采用分子生物学、细胞生物学和免疫学方法，探索TRIM2与A型流感病毒诱导IFN-β表达的关系。预期结果将揭示TRIM2在抗病毒免疫反应中的作用，为开发新的抗病毒策略提供理论基础。该研究对理解宿主抗病毒机制具有重要科学意义，并可能对临床治疗流感病毒感染提供新的视角。

AI项目思路：

科学问题：TRIM2如何调控A型流感病毒诱导的IFN-β表达？
前期研究：已有研究表明TRIM2参与抗病毒反应，但其具体机制尚不明确。
研究创新点：本研究将深入探讨TRIM2在IFN-β表达中的直接作用机制。
技术路线：包括病毒学、分子生物学、细胞培养和免疫检测技术。
关键技术：TRIM2与病毒RNA的相互作用分析，IFN-β启动子活性检测。
实验模型：使用A型流感病毒感染的细胞模型进行研究。

AI技术路线图

        graph TD
          A[研究起始] --> B[文献回顾与假设提出]
          B --> C[实验设计与方法学准备]
          C --> D[A型流感病毒感染模型建立]
          D --> E[TRIM2与病毒RNA相互作用分析]
          E --> F[TRIM2对IFN-β启动子活性的影响]
          F --> G[IFN-β表达水平测定]
          G --> H[TRIM2功能丧失与获得研究]
          H --> I[数据收集与分析]
          I --> J[结果解释与科学验证]
          J --> K[研究结论与未来方向]
          K --> L[研究结束]
关闭
close
客服二维码