检索结果-内蒙古大学图书馆

computational complexity of Yajisan-Kazusan and Stained Glass

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2025年第3期E108D卷 201-207页

作者： Iwamoto, Chuzo Takaishi, Ryo Hiroshima Univ Grad Sch Adv Sci & Engn Higashihiroshima 7398521 Japan

Yajisan-Kazusan and Stained Glass are Nikoli's pencil puzzles. We study the computational complexity of Yajisan-Kazusan and Stained Glass puzzles. It is shown that deciding whether a given instance of each puzzle ... 详细信息

关键词： Yajisan-Kazusan Stained Glass pencil puzzle computational complexity NP-complete

来源：评论

学校读者我要写书评

暂无评论

computational complexity of the recoverable robust shortest path problem with discrete recourse

引用

DISCRETE APPLIED MATHEMATICS 2025年 370卷 103-110页

作者： Jackiewicz, Marcel Kasperski, Adam Zielinski, Pawel Wroclaw Univ Sci & Technol Wroclaw Poland

In this paper, the recoverable robust shortest path problem is investigated. Discrete budgeted interval uncertainty representation is used to model uncertain second-stage arc costs. The known complexity results for this problem are strengthened. Namely, it is shown that the recoverable robust shortest path problem is Sigma(p)(3)-hard for the arc exclusion and arc symmetric difference neighborhoods. Furthermore, it is also proven that the inner adversarial problem for these neighborhoods is Pi(p)(2)-hard. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Robust optimization Interval data Recovery Shortest path computational complexity

来源：评论

学校读者我要写书评

暂无评论

computational complexity OF THE HYLLAND-ZECKHAUSER MECHANISM FOR ONE-SIDED MATCHING MARKETS

引用

SIAM JOURNAL ON COMPUTING 2025年第2期54卷 193-232页

作者： Vazirani, Vijay V. Yannakakis, Mihalis Univ Calif Irvine Irvine CA 92697 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

In 1979, Hylland and Zeckhauser [J. Polit. Econ., 87 (1979), pp. 293--314] gave a simple and general mechanism for a one-sided matching market, given cardinal utilities of agents over goods. They use the power of a pricing mechanism, which endows their mechanism with several desirable properties---it produces an allocation that is Pareto optimal and envy free, and the mechanism is incentive compatible in the large. It therefore provides an attractive, off-the-shelf method for running an application involving such a market. With matching markets becoming ever more prevalent and impactful, it is imperative to characterize the computational complexity of this mechanism. We present the following results: (1) A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 utilities, and more generally, when each agent's utilities come from a bivalued set. (2) An example that has only irrational equilibria;hence this problem is not in PPAD. (3) A proof of membership of the problem in the class FIXP;as a corollary we get that a Hylland--Zeckhauser (HZ) equilibrium can always be expressed via algebraic numbers. For this purpose, we give a new proof of the existence of an HZ equilibrium using Brouwer's fixed point theorem;the proof of Hylland and Zeckhauser used Kakutani's fixed point theorem, which is more involved. (4) A proof of membership of the problem of computing an approximate HZ equilibrium in the class PPAD. In subsequent work [T. Chen et al., SODA 2022, SIAM, Philadelphia, pp. 2253-2268], the problem of computing an approximate HZ equilibrium was shown to be PPAD-hard, thereby establishing it to be PPAD-complete. We leave open the (difficult) question of determining if computing an exact HZ equilibrium is FIXP-hard. We also give pointers to the substantial body of work on cardinal-utility matching markets which followed [V. V. Vazirani and M. Yannakakis, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl, Wadern Germany, 59].

关键词： computational complexity Hylland-Zeckhauser mechanism one-sided matching markets Brouwer's fixed point theorem PPAD FIXP dichotomous utilities

来源：评论

学校读者我要写书评

暂无评论

Tradeoff of computational complexity and Accuracy in SpaceFrequency Time Reversal Imaging

引用

IEEE SENSORS JOURNAL 2025年第3期25卷 4980-4989页

作者： Cheng, Zi-Han Li, Huan Huang, Chaoying Zhao, Deshuang Wang, Bing-Zhong Univ Elect Sci & Technol China Sch Informat & Commun Engn Chengdu 611731 Peoples R China Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200240 Peoples R China Univ Elect Sci & Technol China Sch Phys Chengdu 611731 Peoples R China

Time reversal (TR) has much potential to be used in more intelligent imaging applications. Developed with the TR imaging system of the large-scale array and wide bandwidth, the large elements and high sampling frequencies jointly increase the computational complexity significantly. Meanwhile, the weakened imaging accuracy is always accompanied on account of the reduced computations. To balance the computational complexity and imaging accuracy, this article proposes the optimal truncated space-frequency multiple signal classification (OTSF-MUSIC) imaging method. In this approach, the principal components of space-frequency multistatic data matrix (SF-MDM) are first obtained by the optimal truncated space-frequency (OTSF) operator. Second, the orthogonality between the SF-MDM and the noise space decomposed by the singular value decomposition (SVD) is demonstrated. Finally, the equivalent noise subspace constructed by the OTSF operator, which is proved to be also orthogonal to the SF-MDM, can be used in OTSF-MUSIC. The numerical results show that the proposed OTSF-MUSIC without SVD can save approximately 91% of runtimes and decline the imaging errors of 0.62 lambda(c) at the extremely strong perturbated conditions, which indicates that OTSF-MUSIC achieves a tradeoff between the computational complexity and imaging accuracy.

关键词： computational complexity estimation imaging accuracy space-frequency time reversal (TR) estimation imaging accuracy space-frequency time reversal (TR)

来源：评论

学校读者我要写书评

暂无评论

A Clearing Mechanism with Reduced computational complexity for Spot Flexibility Markets

引用

JOURNAL OF MODERN POWER SYSTEMS AND CLEAN ENERGY 2025年第2期13卷 650-662页

作者： Sabir, Sameer Kelouwani, Sousso Henao, Nilson Toquica, David Fournier, Michael Agbossou, Kodjo Oviedo, Juan C. Univ Quebec Trois Rivieres Dept Elect & Comp Engn Trois Rivieres PQ Canada Univ Quebec Trois Rivieres Dept Mech Engn Trois Rivieres PQ Canada Inst Rech Hydroquebec Lab Technol Energie Shawinigan PQ Canada

The spot flexibility markets are before the real-time energy exchange, allowing demand-side management to reduce energy consumption during peak periods. In these markets, demand aggregators must quickly choose the customers' reduction bids that fulfill grid requirements. This clearing procedure is challenging due to the computational complexity of selecting the optimal bids. Therefore, developing a clearing mechanism that avoids searching the entire flexibility bid space while respecting grid constraints is essential for the smooth operation of the spot flexibility market. This paper presents a clearing mechanism with reduced computational complexity of the winner determination problem in spot flexibility market for demand aggregators carrying out reductions in energy consumption. The proposed approach transforms customers' flexibility bids into a reward-based function. Afterward, the gradient-based optimization solves the bid selection problem. This approach helps demand aggregators achieve satisfactory energy reductions within an appropriate delay for spot flexibility markets. A comparative study presents the effectiveness of the proposed approach against commonly used approaches: hybrid particle swarm optimization genetic algorithm and combinatorial search.

关键词： computational complexity Electricity Real-time systems Indexes Costs Energy consumption Transactive energy Combinatorial auction computational complexity demand response flexibility spot flexibility market transactive energy clearing gradient-based optimization

来源：评论

学校读者我要写书评

暂无评论

Gnss-denied unmanned aerial vehicle navigation: analyzing computational complexity, sensor fusion, and localization methodologies

引用

SATELLITE NAVIGATION 2025年第1期6卷 1-33页

作者： Jarraya, Imen Al-Batati, Abdulrahman Kadri, Muhammad Bilal Abdelkader, Mohamed Ammar, Adel Boulila, Wadii Koubaa, Anis Prince Sultan Univ Coll Comp & Informat Sci Riyadh 11586 Saudi Arabia

Navigation without Global Navigation Satellite Systems (GNSS) poses a significant challenge in aerospace engineering, particularly in the environments where satellite signals are obstructed or unavailable. This paper offers an in-depth review of various methods, sensors, and algorithms for Unmanned Aerial Vehicle (UAV) localization in outdoor environments where GNSS signals are unavailable or denied. A key contribution of this study is the establishment of a critical classification system that divides GNSS-denied navigation techniques into two primary categories: absolute and relative localization. This classification enhances the understanding of the strengths and weaknesses of different strategies in various operational contexts. Vision-based localization is identified as the most effective approach in GNSS-denied environments. Nonetheless, it's clear that no single-sensor-based localization algorithm can fulfill all the needs of a comprehensive navigation system in outdoor environments. Therefore, it's vital to implement a hybrid strategy that merges various algorithms and sensors for effective outcomes. This detailed analysis emphasizes the challenges and possible solutions for achieving reliable and effective outdoor UAV localization in environments where GNSS is unreliable or unavailable. This multi-faceted analysis, highlights the complexities and potential pathways for achieving efficient and dependable outdoor UAV localization in GNSS-denied environments.

关键词： UAV localization GNSS-denied navigation Absolute localization Relative localization Visual sensors Non-visual sensors Terrain aided algorithm Digital map Multi-modal sensor fusion framework Multiple localization techniques computational complexity

来源：评论

学校读者我要写书评

暂无评论

computational complexity, algorithmic scope, and evolution

JOURNAL OF PHYSICS-COMPLEXITY

引用

JOURNAL OF PHYSICS-complexity 2025年第1期6卷

作者： Sidl, Leonhard Faissner, Maximilian Uhlir, Manuel Velandia-Huerto, Cristian A. Waldl, Maria Yao, Hua-Ting Hofacker, Ivo L. Stadler, Peter F. Univ Vienna Dept Theoret Chem Wahringer Str 17 A-1090 Vienna Austria Univ Vienna Res Grp Bioinformat & Computat Biol Wahringer Str 29 A-1090 Vienna Austria Med Univ Vienna Ctr Anat & Cell Biol Schwarzspanierstr 17 A-1090 Vienna Austria Univ Leipzig Dept Comp Sci Bioinformat Grp D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat D-04107 Leipzig Germany Max Planck Inst Math Sci D-04103 Leipzig Germany Santa Fe Inst Santa Fe NM 87501 USA Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany

Biological systems are widely regarded as performing computations. It is much less clear, however, what exactly is computed and how biological computation fits within the framework of standard computer science. Here we explore the idea that evolution confines biological computation to subsets of instances that can be solved efficiently with algorithms that are 'hardcoded' in the system itself. We use RNA secondary structure prediction as a simple surrogate for developmental programs to demonstrate that the salient features of the genotype-phenotype map remain intact even if 'simpler' algorithms are employed that correctly compute the structures only for small subsets of instances, albeit quantitative differences depending on the choice of alternative algorithms can be observed.

关键词： computational complexity biological computation RNA folding developmental program genotype-phenotype map

来源：评论

学校读者我要写书评

暂无评论

computational complexity as a potential limitation on brain-behaviour mapping

引用

EUROPEAN JOURNAL OF NEUROSCIENCE 2025年第1期61卷 e16636页

作者： Ozkirli, Ayberk Herzog, Michael H. Jastrzebowska, Maya A. Ecole Polytech Fed Lausanne EPFL Brain Mind Inst Lab Psychophys Lausanne Switzerland Free Univ Berlin Dept Educ & Psychol Berlin Germany

Within the reductionist framework, researchers in the special sciences formulate key terms and concepts and try to explain them with lower-level science terms and concepts. For example, behavioural vision scientists describe contrast perception with a psychometric function, in which the perceived brightness increases logarithmically with the physical contrast of a light patch (the Weber-Fechner law). Visual neuroscientists describe the output of neural circuits with neurometric functions. Intuitively, the key terms from two adjacent scientific domains should map onto each other;for instance, psychometric and neurometric functions may map onto each other. Identifying such mappings has been the very goal of neuroscience for nearly two centuries. Yet mapping behaviour to brain measures has turned out to be difficult. Here, we provide various arguments as to why the conspicuous lack of robust brain-behaviour mappings is rather a rule than an exception. First, we provide an overview of methodological and conceptual issues that may stand in the way of successful brain-behaviour mapping. Second, extending previous theoretical work (Herzog, Doerig and Sachse, 2023), we show that brain-behaviour mapping may be limited by complexity barriers. In this case, reduction may be impossible.

关键词： brain-behaviour mapping cognitive ontology computational complexity localisationism neural degeneracy

来源：评论

学校读者我要写书评

暂无评论

computational complexity of Polynomial Subalgebras

arXiv

引用

arXiv 2025年

作者： Kayser, Leonie MPI-MiS Leipzig Germany

The computational complexity of polynomial ideals and Gröbner bases has been studied since the 1980s. In recent years the related notions of polynomial subalgebras and SAGBI bases have gained more and more attention in computational algebra, with a view towards effective algorithms. We investigate the computational complexity of the subalgebra membership problem and degree bounds. In particular, we place these problems in the complexity class EXPSPACE and prove PSPACE-completeness for homogeneous algebras. We highlight parallels and differences compared to the settings of ideals and also look at important classes of polynomials such as monomial *** Codes 08A30, 13P10, 14Q20 © 2025, CC BY.

关键词： computational complexity

来源：评论

学校读者我要写书评

暂无评论

COLAFormer: Communicating local-global features with linear computational complexity

引用

PATTERN RECOGNITION 2025年 157卷

作者： Miao, Zhengwei Luo, Hui Li, Meihui Zhang, Jianlin Chinese Acad Sci Natl Key Lab Opt Field Manipulat Sci & Technol Chengdu 610209 Peoples R China Chinese Acad Sci Key Lab Opt Engn Chengdu 610209 Peoples R China Chinese Acad Sci Inst Opt & Elect Chengdu 610209 Peoples R China Univ Chinese Acad Sci Sch Elect Elect & Commun Engn Beijing 108408 Peoples R China

Local and sparse attention effectively reduce the high computational cost of global self-attention. However, they suffer from non-global dependency and coarse feature capturing, respectively. While some subsequent models employ effective interaction techniques for better classification performance, we observe that the computation and memory of these models overgrow as the resolution increases. Consequently, applying them to downstream tasks with large resolutions takes time and effort. In response to this concern, we propose an effective backbone network based on a novel attention mechanism called Concatenating glObal tokens in Local Attention (COLA) with a linear computational complexity. The implementation of COLA is straightforward, as it incorporates global information into the local attention in a concatenating manner. We introduce a learnable condensing feature (LCF) module to capture high-quality global information. LCF possesses the following properties: (1) performing a function similar to clustering, aggregating image patches into a smaller number of tokens based on similarity. (2) a constant number of aggregated tokens regardless of the image size, ensuring that it is a linear complexity operator. Based on COLA, we build COLAFormer, which achieves global dependency and fine-grained feature capturing with linear computational complexity and demonstrates impressive performance across various vision tasks. Specifically, our COLAFormer-S achieves 84.5% classification accuracy, surpassing other advanced models by 0.4% with similar or less resource consumption. Furthermore, our COLAFormer-S can achieve a better object detection performance while consuming only 1/4 of the resources compared to other state-of-the-art models. The code and models will be made publicly available.

关键词： Computer vision Vision transformer Image classification computational complexity Feature clustering

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：