Telegram Group & Telegram Channel
研究确定背包问题计算复杂性下限

2025-06-03 23:25 by 挽救计划

中国科学院金属研究所研究员张志东确定了“背包问题”的计算复杂度下限。研究报告发表在《AIMS数学》(AIMS Mathematics)。“背包问题”是计算机科学中经典的NP完全问题(非确定性图灵机多项式复杂度求解的决定问题)。“背包问题”的目标是,在限制所有物体权重之和小于或等于最大权重的前提下,最大化所有物体的价值之和。“背包问题”可用来进行组合数学、密码学、商业等领域的计算,还可以应用在不同领域的决策,如寻找减少原材料使用、投资组合的选择、密钥产生等最优化搜寻路径。“背包问题”与自旋玻璃模型的联系是,“背包问题”的二元决定性变量对应于自旋向上和自旋向下两种状态。“背包问题”的权重对应于自旋之间的相互作用。“背包问题”的哈密顿量可以映射成具有偏置场的自旋玻璃模型的哈密顿。因此,通过求解自旋玻璃模型可以求解“背包问题”。研究得出结论,背包问题计算复杂度的下限为(1+无限小)的N次方——即O((1+ε)^N)。

www.aimspress.com/article/doi/10.3934/math.2025538
www.cas.cn/syky/202505/t20250530_5071218.shtml

#数学



tg-me.com/solidot/27235
Create:
Last Update:

研究确定背包问题计算复杂性下限

2025-06-03 23:25 by 挽救计划

中国科学院金属研究所研究员张志东确定了“背包问题”的计算复杂度下限。研究报告发表在《AIMS数学》(AIMS Mathematics)。“背包问题”是计算机科学中经典的NP完全问题(非确定性图灵机多项式复杂度求解的决定问题)。“背包问题”的目标是,在限制所有物体权重之和小于或等于最大权重的前提下,最大化所有物体的价值之和。“背包问题”可用来进行组合数学、密码学、商业等领域的计算,还可以应用在不同领域的决策,如寻找减少原材料使用、投资组合的选择、密钥产生等最优化搜寻路径。“背包问题”与自旋玻璃模型的联系是,“背包问题”的二元决定性变量对应于自旋向上和自旋向下两种状态。“背包问题”的权重对应于自旋之间的相互作用。“背包问题”的哈密顿量可以映射成具有偏置场的自旋玻璃模型的哈密顿。因此,通过求解自旋玻璃模型可以求解“背包问题”。研究得出结论,背包问题计算复杂度的下限为(1+无限小)的N次方——即O((1+ε)^N)。

www.aimspress.com/article/doi/10.3934/math.2025538
www.cas.cn/syky/202505/t20250530_5071218.shtml

#数学

BY Solidot


Warning: Undefined variable $i in /var/www/tg-me/post.php on line 283

Share with your friend now:
tg-me.com/solidot/27235

View MORE
Open in Telegram


Solidot Telegram | DID YOU KNOW?

Date: |

At a time when the Indian stock market is peaking and has rallied immensely compared to global markets, there are companies that have not performed in the last 10 years. These are definitely a minor portion of the market considering there are hundreds of stocks that have turned multibagger since 2020. What went wrong with these stocks? Reasons vary from corporate governance, sectoral weakness, company specific and so on. But the more important question is, are these stocks worth buying?

How to Use Bitcoin?

n the U.S. people generally use Bitcoin as an alternative investment, helping diversify a portfolio apart from stocks and bonds. You can also use Bitcoin to make purchases, but the number of vendors that accept the cryptocurrency is still limited. Big companies that accept Bitcoin include Overstock, AT&T and Twitch. You may also find that some small local retailers or certain websites take Bitcoin, but you’ll have to do some digging. That said, PayPal has announced that it will enable cryptocurrency as a funding source for purchases this year, financing purchases by automatically converting crypto holdings to fiat currency for users. “They have 346 million users and they’re connected to 26 million merchants,” says Spencer Montgomery, founder of Uinta Crypto Consulting. “It’s huge.”

Solidot from us


Telegram Solidot
FROM USA