会员服务
边 · 离散数学 · 算法与数据结构 · 博弈论 ·
2022 年 11 月 18 日
Avoider-Enforcer Game is NP-hard
翻译：NP- 硬化的避免- 启动者游戏
Tillmann Miltzow,Miloš Stojaković
Tillmann Miltzow,Miloš Stojaković
from arxiv, 8 pages, 3 figures

In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enforcer alternate in claiming an unclaimed vertex, until all the vertices of the hypergraph are claimed. Enforcer wins if Avoider claims all vertices of an edge; Avoider wins otherwise. We show that it is NP-hard to decide if Avoider has a winning strategy.


翻译：在避险者-强制者游戏中,我们被授予了高射线。 避险者和强制者轮流主张一个无人认领的脊椎, 直到高射线的所有脊椎被主张为止。 如果避险者声称有边缘的所有脊椎, 强制者胜出; 避险者则胜出。 我们证明NP很难决定避险者是否有胜出策略 。
0
下载
关闭预览

相关内容

不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
专知会员服务
74+阅读 · 2022年6月28日
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
专知会员服务
76+阅读 · 2022年3月15日
Linux导论，Introduction to Linux，96页ppt
Linux导论，Introduction to Linux，96页ppt
专知会员服务
79+阅读 · 2020年7月26日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
92+阅读 · 2020年2月12日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
49+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
35+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
专知会员服务
79+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
函数空间、几何和Mahler测度
国家自然科学基金
0+阅读 · 2014年12月31日
Navier-Stokes 方程组的若干存在性问题
国家自然科学基金
0+阅读 · 2014年12月31日
量子群与Tewilliger代数的相关问题研究
国家自然科学基金
1+阅读 · 2013年12月31日
有关四阶Monge-Ampere型方程若干问题的研究
国家自然科学基金
0+阅读 · 2013年12月31日
Calderon问题和边界刚性问题
国家自然科学基金
0+阅读 · 2013年12月31日
可压缩Navier-Stokes方程和Boltzmann方程解的渐近行为
国家自然科学基金
0+阅读 · 2013年12月31日
间断Galerkin方法及在电磁计算中的应用研究
国家自然科学基金
0+阅读 · 2013年12月31日
Intraflagellar Transport运输纤毛蛋白的分子机理
国家自然科学基金
0+阅读 · 2012年12月31日
LncRNAs在非小细胞肺癌EGFR-TKIs耐药中的作用及分子机制
国家自然科学基金
0+阅读 · 2012年12月31日
能量临界情形的非线性Schrodinger方程
国家自然科学基金
0+阅读 · 2011年12月31日
Three aspects of the MSTCI problem
Three aspects of the MSTCI problem
Arxiv
0+阅读 · 2023年1月18日
Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning
Arxiv
0+阅读 · 2023年1月18日
Homogenization and numerical algorithms for two-scale modelling of porous media with self-contact in micropores
Arxiv
0+阅读 · 2023年1月17日
Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes
Arxiv
0+阅读 · 2023年1月17日
Fully Elman Neural Network: A Novel Deep Recurrent Neural Network Optimized by an Improved Harris Hawks Algorithm for Classification of Pulmonary Arterial Wedge Pressure
Arxiv
0+阅读 · 2023年1月16日
Haptic Transparency and Interaction Force Control for a Lower-Limb Exoskeleton
Arxiv
0+阅读 · 2023年1月16日
Balanced Allocations with the Choice of Noise
Arxiv
0+阅读 · 2023年1月14日
Thou Shalt not Pick all Items if Thou are First: of Strategyproof and Fair Picking Sequences
Arxiv
0+阅读 · 2023年1月11日
The Role of Heterogeneity in Autonomous Perimeter Defense Problems
The Role of Heterogeneity in Autonomous Perimeter Defense Problems
Arxiv
13+阅读 · 2022年2月21日
Multi-Agent Cooperative Bidding Games for Multi-Objective Optimization in e-Commercial Sponsored Search
Arxiv
12+阅读 · 2021年6月8日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
边
离散数学
算法与数据结构
博弈论
相关VIP内容
不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
不可错过！《机器学习100讲》课程，UBC Mark Schmidt讲授
专知会员服务
74+阅读 · 2022年6月28日
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
专知会员服务
76+阅读 · 2022年3月15日
Linux导论，Introduction to Linux，96页ppt
Linux导论，Introduction to Linux，96页ppt
专知会员服务
79+阅读 · 2020年7月26日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
92+阅读 · 2020年2月12日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
49+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
35+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
58+阅读 · 2019年10月17日
机器学习入门的经验与建议
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
专知会员服务
79+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
热门VIP内容
相关资讯
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium7
中国图象图形学学会CSIG
0+阅读 · 2021年11月15日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
相关论文
Three aspects of the MSTCI problem
Three aspects of the MSTCI problem
Arxiv
0+阅读 · 2023年1月18日
Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning
Arxiv
0+阅读 · 2023年1月18日
Homogenization and numerical algorithms for two-scale modelling of porous media with self-contact in micropores
Arxiv
0+阅读 · 2023年1月17日
Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes
Arxiv
0+阅读 · 2023年1月17日
Fully Elman Neural Network: A Novel Deep Recurrent Neural Network Optimized by an Improved Harris Hawks Algorithm for Classification of Pulmonary Arterial Wedge Pressure
Arxiv
0+阅读 · 2023年1月16日
Haptic Transparency and Interaction Force Control for a Lower-Limb Exoskeleton
Arxiv
0+阅读 · 2023年1月16日
Balanced Allocations with the Choice of Noise
Arxiv
0+阅读 · 2023年1月14日
Thou Shalt not Pick all Items if Thou are First: of Strategyproof and Fair Picking Sequences
Arxiv
0+阅读 · 2023年1月11日
The Role of Heterogeneity in Autonomous Perimeter Defense Problems
The Role of Heterogeneity in Autonomous Perimeter Defense Problems
Arxiv
13+阅读 · 2022年2月21日
Multi-Agent Cooperative Bidding Games for Multi-Objective Optimization in e-Commercial Sponsored Search
Arxiv
12+阅读 · 2021年6月8日
相关基金
函数空间、几何和Mahler测度
国家自然科学基金
0+阅读 · 2014年12月31日
Navier-Stokes 方程组的若干存在性问题
国家自然科学基金
0+阅读 · 2014年12月31日
量子群与Tewilliger代数的相关问题研究
国家自然科学基金
1+阅读 · 2013年12月31日
有关四阶Monge-Ampere型方程若干问题的研究
国家自然科学基金
0+阅读 · 2013年12月31日
Calderon问题和边界刚性问题
国家自然科学基金
0+阅读 · 2013年12月31日
可压缩Navier-Stokes方程和Boltzmann方程解的渐近行为
国家自然科学基金
0+阅读 · 2013年12月31日
间断Galerkin方法及在电磁计算中的应用研究
国家自然科学基金
0+阅读 · 2013年12月31日
Intraflagellar Transport运输纤毛蛋白的分子机理
国家自然科学基金
0+阅读 · 2012年12月31日
LncRNAs在非小细胞肺癌EGFR-TKIs耐药中的作用及分子机制
国家自然科学基金
0+阅读 · 2012年12月31日
能量临界情形的非线性Schrodinger方程
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员
Top