电路的复杂性和功能:从统计热力学角度来看
Claudio Chamon1, Andrei E Ruckenstein1, Eduardo R Mucciolo2
1Department of Physics, Boston University, Boston, MA 02215.
概括
这项研究将电路复杂性和热力学联系起来,为程序模糊提供了一个新的视角. 它揭示了循环混合如何平衡电路复杂性和,保持功能.
科学领域:
- 理论计算机科学 理论计算机科学
- 量子信息理论 量子信息理论
- 计算复杂性 计算复杂性
背景情况:
- 电路复杂性,布尔计算的最小大小,是一个基本的,但很难的计算问题.
- 电路复杂性最近与黑洞物理学中的物理性质有关,特别是虫洞中复杂性的增长.
- 了解程序模糊对于密码学至关重要,旨在隐藏程序的功能.
研究的目的:
- 探索电路复杂性与功能等效电路的热力学之间的关系.
- 开发一个热力学框架来理解程序模糊.
- 调查电路碎片化对计算复杂性类别的影响.
主要方法:
- 开发了一个热力学框架来分析电路复杂性.
- 模拟程序模糊化作为通过回复混合电路部分的热化.
- 在电路空间中利用了ergodicity和碎片化的概念.
主要成果:
- 证明递归混合平衡了平均电路复杂性,同时保持了功能的电路和电路.
- 引入了碎片化的概念,这意味着功能等价的电路可能无法通过局部移动进行转换.
- 证明碎片化是不可避免的,除非NP和coNP一致,从而崩了多项式层次结构.
结论:
- 热力学方法为程序模糊和电路复杂性提供了一个新的视角.
- 电路碎片化对密码学和计算复杂性理论有重大影响.
- 这些发现表明,物理概念与计算机科学的基本问题之间存在着深厚的联系.
相关概念视频
Circuit Terminology
2.2K
An electrical network is a system composed of interconnected elements, such as resistors, capacitors, inductors, and voltage or current sources. Unlike a circuit, an electrical network does not necessarily form a closed path. In other words, while all circuits can be considered networks due to their interconnected nature, not every network qualifies as a circuit.
A circuit, on the other hand, is also an interconnected system of electrical elements but must contain one or more closed paths.
A circuit, on the other hand, is also an interconnected system of electrical elements but must contain one or more closed paths.
2.2K
Electric Circuit Elements
1.4K
Circuit elements are the basic building blocks of an electric circuit. Essentially, an electric circuit is the interconnection of these elements. Within electric circuits, one can find two types of elements: passive and active. Active elements have the ability to generate energy, whereas passive elements do not. Passive elements include components like resistors, capacitors, and inductors, while active elements typically encompass generators, batteries, and operational amplifiers.
The most...
The most...
1.4K
Thévenin Equivalent Circuits
370
The household power distribution system, encompassing distribution lines and transformers, serves as the primary network. Electrical appliances within a household can be represented as load impedance. To simplify this intricate distribution system, Thévenin's theorem can be applied to create a Thévenin equivalent circuit. If an AC circuit is partitioned into two parts (circuit A and circuit B), connected by a single pair of terminals as shown in Figure 1.
370
Thevinin's Theorem
811
Thévenin's theorem plays a pivotal role in electrical circuit analysis, offering a solution to the challenges posed by variable loads within a circuit. In practical applications, it is common to encounter circuits where certain elements remain fixed while others fluctuate, often referred to as the "load." A typical household electrical outlet serves as a prime example of a variable load, as it can be connected to a variety of appliances, each with its own unique electrical...
811
Path Between Thermodynamics States
3.4K
Consider the two thermodynamic processes involving an ideal gas that are represented by paths AC and ABC in Figure 1:
3.4K
First Law Of Thermodynamics: Problem-Solving
3.0K
The first law of thermodynamics states that the change in internal energy of the system is equal to the net heat transfer into the system minus the net work done by the system. This equation is a generalized form of energy conservation and can be applied to any thermodynamic process.
The following strategies can be used to solve any problem involving the first law of thermodynamics.
The following strategies can be used to solve any problem involving the first law of thermodynamics.
3.0K


