将CELSTE分类为 NP 完成 (Classifying CELESTE as NP Complete) - 专知论文

会员服务 ·

0

CC · entity ·

2022 年 12 月 1 日

Classifying CELESTE as NP Complete

翻译：将CELSTE分类为 NP 完成

Zeeshan Ahmed,Alapan Chaudhuri,Kunwar Shaanjeet Singh Grover,Ashwin Rao,Kushagra Garg,Pulak Malhotra

from arxiv, Keywords: complexity analysis, NP completeness, algorithmic analysis, game analysis

We analyze the computational complexity of the video game "CELESTE" and prove that solving a generalized level in it is NP-Complete. Further, we also show how, upon introducing a small change in the game mechanics (adding a new game entity), we can make it PSPACE-complete.

翻译：我们分析了电子游戏“CELESTE”的计算复杂性,并证明解决它的普遍水平是NP-Compllete。此外,我们还展示了在引入游戏机械学的小改变(添加一个新的游戏实体)后,我们如何能够让它完成PSPACE。

0

相关内容

CC在计算复杂性方面表现突出。它的学科处于数学与计算机理论科学的交叉点，具有清晰的数学轮廓和严格的数学格式。官网链接：https://link.springer.com/journal/37

NeurlPS 2022 | 自然语言处理相关论文分类整理

NeurlPS 2022 | 自然语言处理相关论文分类整理

专知会员服务

48+阅读 · 2022年10月2日

NLP必读经典文献100篇

专知会员服务

123+阅读 · 2020年9月8日

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

专知会员服务

94+阅读 · 2020年3月12日

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

专知会员服务

34+阅读 · 2019年10月17日

Keras François Chollet 《Deep Learning with Python 》, 386页pdf

Keras François Chollet 《Deep Learning with Python 》, 386页pdf

专知会员服务

151+阅读 · 2019年10月12日

开源书：PyTorch深度学习起步

开源书：PyTorch深度学习起步

专知会员服务

50+阅读 · 2019年10月11日

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

专知会员服务

81+阅读 · 2019年10月9日

【加州大学伯克利分校博士论文】通过自我监督预测学习泛化

【加州大学伯克利分校博士论文】通过自我监督预测学习泛化

专知会员服务

64+阅读 · 2019年10月9日

【哈佛大学商学院课程Fall 2019】机器学习可解释性

【哈佛大学商学院课程Fall 2019】机器学习可解释性

专知会员服务

103+阅读 · 2019年10月9日

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

专知会员服务

39+阅读 · 2019年10月9日

Hierarchically Structured Meta-learning

Hierarchically Structured Meta-learning

CreateAMind

26+阅读 · 2019年5月22日

Transferring Knowledge across Learning Processes

Transferring Knowledge across Learning Processes

CreateAMind

27+阅读 · 2019年5月18日

强化学习的Unsupervised Meta-Learning

强化学习的Unsupervised Meta-Learning

CreateAMind

17+阅读 · 2019年1月7日

Unsupervised Learning via Meta-Learning

Unsupervised Learning via Meta-Learning

CreateAMind

42+阅读 · 2019年1月3日

【SIGIR2018】五篇对抗训练文章

【SIGIR2018】五篇对抗训练文章

专知

12+阅读 · 2018年7月9日

【论文推荐】最新6篇生成式对抗网络（GAN）相关论文—半监督对抗学习、行人再识别、代表性特征、高分辨率深度卷积、自监督、超分辨

【论文推荐】最新6篇生成式对抗网络（GAN）相关论文—半监督对抗学习、行人再识别、代表性特征、高分辨率深度卷积、自监督、超分辨

专知

10+阅读 · 2018年2月1日

【论文】变分推断（Variational inference)的总结

【论文】变分推断（Variational inference)的总结

机器学习研究会

39+阅读 · 2017年11月16日

Capsule Networks解析

Capsule Networks解析

机器学习研究会

11+阅读 · 2017年11月12日

【推荐】GAN架构入门综述(资源汇总)

【推荐】GAN架构入门综述(资源汇总)

机器学习研究会

10+阅读 · 2017年9月3日

【推荐】SVM实例教程

【推荐】SVM实例教程

机器学习研究会

17+阅读 · 2017年8月26日

广义Lorenz系统族解的有界性研究

国家自然科学基金

0+阅读 · 2015年12月31日

几类含∞-Laplace算子的特征值问题的研究

国家自然科学基金

1+阅读 · 2015年12月31日

Pnma型IV-VI族化合物单晶的热电性能及其各向异性的理论研究

国家自然科学基金

0+阅读 · 2015年12月31日

复合空馈阵天线的研究与应用

国家自然科学基金

0+阅读 · 2013年12月31日

可见光响应型二氧化钛/石墨烯磁性复合光催化剂催化氧化去除微囊藻毒素研究

国家自然科学基金

0+阅读 · 2013年12月31日

新变指标Besov-Triebel-Lizorkin型函数空间及算子有界性

国家自然科学基金

0+阅读 · 2012年12月31日

含极性非质子溶剂的离子液体-kosmotropic盐双水相体系的研究

国家自然科学基金

0+阅读 · 2012年12月31日

Stra8及其相互作用蛋白Setd8在精子发生中的作用机制

国家自然科学基金

0+阅读 · 2012年12月31日

负载型纳米铁氧化吸附去除饮用水中As(III)的应用基础研究

国家自然科学基金

0+阅读 · 2011年12月31日

Lefty蛋白抗积水肾纤维化作用及其机制研究

国家自然科学基金

0+阅读 · 2011年12月31日

Better Training of GFlowNets with Local Credit and Incomplete Trajectories

Arxiv

0+阅读 · 2023年2月3日

Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series

Arxiv

0+阅读 · 2023年2月3日

Online Verification of Deep Neural Networks under Domain Shift or Network Updates

Arxiv

0+阅读 · 2023年2月3日

Order but Not Execute in Order

Arxiv

0+阅读 · 2023年2月2日

Neural Networks for Symbolic Regression

Arxiv

0+阅读 · 2023年2月1日

Simplicity Bias in 1-Hidden Layer Neural Networks

Arxiv

0+阅读 · 2023年2月1日

What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?

Arxiv

0+阅读 · 2023年2月1日

Compositional GAN: Learning Conditional Image Composition

Compositional GAN: Learning Conditional Image Composition

Arxiv

31+阅读 · 2018年7月19日

Multi-pseudo Regularized Label for Generated Samples in Person Re-Identification

Arxiv

12+阅读 · 2018年1月29日

Re-ID done right: towards good practices for person re-identification

Arxiv

13+阅读 · 2018年1月16日

VIP会员

文章信息

相关主题

相关VIP内容

NeurlPS 2022 | 自然语言处理相关论文分类整理

NeurlPS 2022 | 自然语言处理相关论文分类整理

专知会员服务

48+阅读 · 2022年10月2日

NLP必读经典文献100篇

专知会员服务

123+阅读 · 2020年9月8日

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》

专知会员服务

94+阅读 · 2020年3月12日

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs

专知会员服务

34+阅读 · 2019年10月17日

Keras François Chollet 《Deep Learning with Python 》, 386页pdf

Keras François Chollet 《Deep Learning with Python 》, 386页pdf

专知会员服务

151+阅读 · 2019年10月12日

开源书：PyTorch深度学习起步

开源书：PyTorch深度学习起步

专知会员服务

50+阅读 · 2019年10月11日

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

【CMU卡内基梅隆大学】深度学习在计算机视觉的应用：方法，解释，因果与公平性

专知会员服务

81+阅读 · 2019年10月9日

【加州大学伯克利分校博士论文】通过自我监督预测学习泛化

【加州大学伯克利分校博士论文】通过自我监督预测学习泛化

专知会员服务

64+阅读 · 2019年10月9日

【哈佛大学商学院课程Fall 2019】机器学习可解释性

【哈佛大学商学院课程Fall 2019】机器学习可解释性

专知会员服务

103+阅读 · 2019年10月9日

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用

专知会员服务

39+阅读 · 2019年10月9日

热门VIP内容

相关资讯

Hierarchically Structured Meta-learning

Hierarchically Structured Meta-learning

CreateAMind

26+阅读 · 2019年5月22日

Transferring Knowledge across Learning Processes

Transferring Knowledge across Learning Processes

CreateAMind

27+阅读 · 2019年5月18日

强化学习的Unsupervised Meta-Learning

强化学习的Unsupervised Meta-Learning

CreateAMind

17+阅读 · 2019年1月7日

Unsupervised Learning via Meta-Learning

Unsupervised Learning via Meta-Learning

CreateAMind

42+阅读 · 2019年1月3日

【SIGIR2018】五篇对抗训练文章

【SIGIR2018】五篇对抗训练文章

专知

12+阅读 · 2018年7月9日

【论文推荐】最新6篇生成式对抗网络（GAN）相关论文—半监督对抗学习、行人再识别、代表性特征、高分辨率深度卷积、自监督、超分辨

【论文推荐】最新6篇生成式对抗网络（GAN）相关论文—半监督对抗学习、行人再识别、代表性特征、高分辨率深度卷积、自监督、超分辨

专知

10+阅读 · 2018年2月1日

【论文】变分推断（Variational inference)的总结

【论文】变分推断（Variational inference)的总结

机器学习研究会

39+阅读 · 2017年11月16日

Capsule Networks解析

Capsule Networks解析

机器学习研究会

11+阅读 · 2017年11月12日

【推荐】GAN架构入门综述(资源汇总)

【推荐】GAN架构入门综述(资源汇总)

机器学习研究会

10+阅读 · 2017年9月3日

【推荐】SVM实例教程

【推荐】SVM实例教程

机器学习研究会

17+阅读 · 2017年8月26日

相关论文

Better Training of GFlowNets with Local Credit and Incomplete Trajectories

Arxiv

0+阅读 · 2023年2月3日

Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series

Arxiv

0+阅读 · 2023年2月3日

Online Verification of Deep Neural Networks under Domain Shift or Network Updates

Arxiv

0+阅读 · 2023年2月3日

Order but Not Execute in Order

Arxiv

0+阅读 · 2023年2月2日

Neural Networks for Symbolic Regression

Arxiv

0+阅读 · 2023年2月1日

Simplicity Bias in 1-Hidden Layer Neural Networks

Arxiv

0+阅读 · 2023年2月1日

What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?

Arxiv

0+阅读 · 2023年2月1日

Compositional GAN: Learning Conditional Image Composition

Compositional GAN: Learning Conditional Image Composition

Arxiv

31+阅读 · 2018年7月19日

Multi-pseudo Regularized Label for Generated Samples in Person Re-Identification

Arxiv

12+阅读 · 2018年1月29日

Re-ID done right: towards good practices for person re-identification

Arxiv

13+阅读 · 2018年1月16日

相关基金

广义Lorenz系统族解的有界性研究

国家自然科学基金

0+阅读 · 2015年12月31日

几类含∞-Laplace算子的特征值问题的研究

国家自然科学基金

1+阅读 · 2015年12月31日

Pnma型IV-VI族化合物单晶的热电性能及其各向异性的理论研究

国家自然科学基金

0+阅读 · 2015年12月31日

复合空馈阵天线的研究与应用

国家自然科学基金

0+阅读 · 2013年12月31日

可见光响应型二氧化钛/石墨烯磁性复合光催化剂催化氧化去除微囊藻毒素研究

国家自然科学基金

0+阅读 · 2013年12月31日

新变指标Besov-Triebel-Lizorkin型函数空间及算子有界性

国家自然科学基金

0+阅读 · 2012年12月31日

含极性非质子溶剂的离子液体-kosmotropic盐双水相体系的研究

国家自然科学基金

0+阅读 · 2012年12月31日

Stra8及其相互作用蛋白Setd8在精子发生中的作用机制

国家自然科学基金

0+阅读 · 2012年12月31日

负载型纳米铁氧化吸附去除饮用水中As(III)的应用基础研究

国家自然科学基金

0+阅读 · 2011年12月31日

Lefty蛋白抗积水肾纤维化作用及其机制研究

国家自然科学基金

0+阅读 · 2011年12月31日

微信扫码咨询专知VIP会员