Log in

Relevant bibliographies by topics / Computationally hard problems

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'Computationally hard problems'

Author: Grafiati

Published: 3 June 2025

Last updated: 31 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Computationally hard problems.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Computationally hard problems"

1

Ashok, B., and T. K. Patra. "Locating phase transitions in computationally hard problems." Pramana 75, no. 3 (2010): 549–63. http://dx.doi.org/10.1007/s12043-010-0138-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Schleitzer, Agnes, and Olaf Beyersdorff. "Computationally Hard Problems Are Hard for QBF Proof Systems Too." Proceedings of the AAAI Conference on Artificial Intelligence 39, no. 11 (2025): 11336–44. https://doi.org/10.1609/aaai.v39i11.33233.

Full text

Abstract:

There has been tremendous progress in the past decade in the field of quantified Boolean formulas (QBF), both in practical solving as well as in creating a theory of corresponding proof systems and their proof complexity analysis. Both for solving and for proof complexity, it is important to have interesting formula families on which we can test solvers and gauge the strength of the proof systems. There are currently few such formula families in the literature. We initiate a general programme how to transform computationally hard problems (located in the polynomial hierarchy) into QBFs hard fo

APA, Harvard, Vancouver, ISO, and other styles

3

Chiu, D. T., E. Pezzoli, H. Wu, A. D. Stroock, and G. M. Whitesides. "Using three-dimensional microfluidic networks for solving computationally hard problems." Proceedings of the National Academy of Sciences 98, no. 6 (2001): 2961–66. http://dx.doi.org/10.1073/pnas.061014198.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Žerovnik, Janez. "Heuristics for NP-hard optimization problems - simpler is better!?" Logistics & Sustainable Transport 6, no. 1 (2015): 1–10. http://dx.doi.org/10.1515/jlst-2015-0006.

Full text

Abstract:

Abstract We provide several examples showing that local search, the most basic metaheuristics, may be a very competitive choice for solving computationally hard optimization problems. In addition, generation of starting solutions by greedy heuristics should be at least considered as one of very natural possibilities. In this critical survey, selected examples discussed include the traveling salesman, the resource-constrained project scheduling, the channel assignment, and computation of bounds for the Shannon capacity.

APA, Harvard, Vancouver, ISO, and other styles

5

Zaikin, Oleg, Pavel Petrov, Mikhail Posypkin, Vadim Bulavintsev, and Ilya Kurochkin. "A Volunteer Computing Project for Solving Geoacoustic Inversion Problems." Open Engineering 7, no. 1 (2017): 363–70. http://dx.doi.org/10.1515/eng-2017-0040.

Full text

Abstract:

AbstractA volunteer computing project aimed at solving computationally hard inverse problems in underwater acoustics is described. This project was used to study the possibilities of the sound speed profile reconstruction in a shallow-water waveguide using a dispersion-based geoacoustic inversion scheme. The computational capabilities provided by the project allowed us to investigate the accuracy of the inversion for different mesh sizes of the sound speed profile discretization grid. This problem suits well for volunteer computing because it can be easily decomposed into independent simpler s

APA, Harvard, Vancouver, ISO, and other styles

6

Dean, Walter. "Computational Complexity Theory and the Philosophy of Mathematics†." Philosophia Mathematica 27, no. 3 (2019): 381–439. http://dx.doi.org/10.1093/philmat/nkz021.

Full text

Abstract:

Abstract Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ problem and why it has

APA, Harvard, Vancouver, ISO, and other styles

7

Lauri, Juho, and Sourav Dutta. "Fine-Grained Search Space Classification for Hard Enumeration Variants of Subset Problems." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2314–21. http://dx.doi.org/10.1609/aaai.v33i01.33012314.

Full text

Abstract:

We propose a simple, powerful, and flexible machine learning framework for (i) reducing the search space of computationally difficult enumeration variants of subset problems and (ii) augmenting existing state-of-the-art solvers with informative cues arising from the input distribution. We instantiate our framework for the problem of listing all maximum cliques in a graph, a central problem in network analysis, data mining, and computational biology. We demonstrate the practicality of our approach on real-world networks with millions of vertices and edges by not only retaining all optimal solut

APA, Harvard, Vancouver, ISO, and other styles

8

DANTSIN, EVGENY, and ALEXANDER WOLPERT. "A ROBUST DNA COMPUTATION MODEL THAT CAPTURES PSPACE." International Journal of Foundations of Computer Science 14, no. 05 (2003): 933–51. http://dx.doi.org/10.1142/s0129054103002096.

Full text

Abstract:

One of the most serious problems in DNA computing is that basic DNA operations are faulty. Many DNA computation models use operations based on annealing and magnetic-beads separation which sometimes produce undesirable results. Some models use reliable operations only but their computational power is too weak. The purpose of this paper is to find a good trade-off between the robustness of DNA operations and their computational power. We present a robust DNA computation model that can solve computationally hard problems. We prove that (i) this model can solve PSPACE-complete problems, and (ii)

APA, Harvard, Vancouver, ISO, and other styles

9

LIU, JIMING, XIAOLONG JIN, and JING HAN. "DISTRIBUTED PROBLEM SOLVING WITHOUT COMMUNICATION — AN EXAMINATION OF COMPUTATIONALLY HARD SATISFIABILITY PROBLEMS." International Journal of Pattern Recognition and Artificial Intelligence 16, no. 08 (2002): 1041–64. http://dx.doi.org/10.1142/s0218001402002143.

Full text

Abstract:

In this paper, we extend and modify the ERA approach proposed in Ref. 13 to solve Propositional Satisfiability Problems (SATs). The new ERA approach involves a multiagent system where each agent only senses its local environment and applies some self-organizing rules for governing its movements. The environment, which is a two-dimensional cellular environment, records and updates the local values that are computed and affected according to the movements of individual agents. In solving a SAT with the ERA approach, we first divide variables into several groups, and represent each variable group

APA, Harvard, Vancouver, ISO, and other styles

10

Kel’manov, A. V., and S. M. Romanchenko. "Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems." Automation and Remote Control 73, no. 2 (2012): 349–54. http://dx.doi.org/10.1134/s0005117912020129.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Computationally hard problems"

1

Chen, Jiehua [Verfasser], Rolf [Akademischer Betreuer] Niedermeier, Rolf [Gutachter] Niedermeier, Jérôme [Gutachter] Lang, and Edith [Gutachter] Elkind. "Exploiting structure in computationally hard voting problems / Jiehua Chen ; Gutachter: Rolf Niedermeier, Jérôme Lang, Edith Elkind ; Betreuer: Rolf Niedermeier." Berlin : Universitätsverlag der TU Berlin, 2016. http://d-nb.info/1156336538/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hutter, Frank. "Automated configuration of algorithms for solving hard computational problems." Thesis, University of British Columbia, 2009. http://hdl.handle.net/2429/13907.

Full text

Abstract:

The best-performing algorithms for many hard problems are highly parameterized. Selecting the best heuristics and tuning their parameters for optimal overall performance is often a difficult, tedious, and unsatisfying task. This thesis studies the automation of this important part of algorithm design: the configuration of discrete algorithm components and their continuous parameters to construct an algorithm with desirable empirical performance characteristics. Automated configuration procedures can facilitate algorithm development and be applied on the end user side to optimize performance fo

APA, Harvard, Vancouver, ISO, and other styles

3

Ono, Satoshi. "In pursuit of NP-hard combinatorial optimization problems." Diss., Online access via UMI:, 2009.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Canzar, Stefan. "Lagrangian Relaxation - Solving NP-hard Problems in Computational Biology via Combinatorial Optimization." Phd thesis, Université Henri Poincaré - Nancy I, 2008. http://tel.archives-ouvertes.fr/tel-00388521.

Full text

Abstract:

This thesis is devoted to two $\mathcal{NP}$-complete combinatorial optimization problems arising in computational biology, the well-studied \emph{multiple sequence alignment} problem and the new formulated \emph{interval constraint coloring} problem. It shows that advanced mathematical programming techniques are capable of solving large scale real-world instances from biology to optimality. Furthermore, it reveals alternative methods that provide approximate solutions. In the first part of the thesis, we present a \emph{Lagrangian relaxation} approach for the multiple sequence alignment (MSA)

APA, Harvard, Vancouver, ISO, and other styles

5

Nyamugure, Philimon. "Modification, development, application and computational experiments of some selected network, distribution and resource allocation models in operations research." Thesis, University of Limpopo, 2017. http://hdl.handle.net/10386/1930.

Full text

Abstract:

Thesis (Ph.D. (Statistics)) -- University of Limpopo, 2017<br>Operations Research (OR) is a scientific method for developing quantitatively well-grounded recommendations for decision making. While it is true that it uses a variety of mathematical techniques, OR has a much broader scope. It is in fact a systematic approach to solving problems, which uses one or more analytical tools in the process of analysis. Over the years, OR has evolved through different stages. This study is motivated by new real-world challenges needed for efficiency and innovation in line with the aims and objectiv

APA, Harvard, Vancouver, ISO, and other styles

6

Holm, Cyril. "F. A. Hayek's Critique of Legislation." Doctoral thesis, Uppsala universitet, Juridiska institutionen, 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-236890.

Full text

Abstract:

The dissertation concerns F. A. Hayek’s (1899–1992) critique of legislation. The purpose of the investigation is to clarify and assess that critique. I argue that there is in Hayek’s work a critique of legislation that is distinct from his well-known critique of social planning. Further that the main claim of this critique is what I refer to as Hayek’s legislation tenet, namely that legislation that aims to achieve specific aggregate results in complex orders of society will decrease the welfare level. The legislation tenet gains support; (i) from the welfare claim – according to whi

APA, Harvard, Vancouver, ISO, and other styles

7

Carruthers, Sarah. "The Role of the Goal in Problem Solving Hard Computational Problems: Do People Really Optimize?" Thesis, 2015. http://hdl.handle.net/1828/6666.

Full text

Abstract:

Understanding how humans cope with complexity is perhaps one of the most important targets of scientific research. Humans not only excel at solving complex tasks in their day to day life but also take on objectively difficult problems recreationally. Research, which has focused to date on the famous hard optimization problem the Euclidean Traveling Salesperson problem (E-TSP), has indicated that humans are able to find near optimal solutions in linear time to hard optimization problems despite the objective difficulty of the task. The research presented in this work contributes to this researc

APA, Harvard, Vancouver, ISO, and other styles

8

Hajiaghaei, Shanjani Sima. "Computational and communication complexity of geometric problems." Thesis, 2021. http://hdl.handle.net/1828/13181.

Full text

Abstract:

In this dissertation, we investigate a number of geometric problems in different settings. We present lower bounds and approximation algorithms for geometric problems in sequential and distributed settings. For the sequential setting, we prove the first hardness of approximation results for the following problems: \begin{itemize} \item Red-Blue Geometric Set Cover is APX-hard when the objects are axis-aligned rectangles. \item Red-Blue Geometric Set Cover cannot be approximated to within $2^{\log^{1-1/{(\log\log m)^c}}m}$ in polynomial time for any constant $c < 1/2$, unless

APA, Harvard, Vancouver, ISO, and other styles

9

Grant, Elyot. "Covering Problems via Structural Approaches." Thesis, 2011. http://hdl.handle.net/10012/6317.

Full text

Abstract:

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms

APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Computationally hard problems"

1

Nisan, Noam. Using hard problems to create pseudorandom generators. MIT Press, 1992.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hromkovič, Juraj. Algorithmics for hard problems: Introduction to combinatorial optimization, randomization, approximation, and heuristics, with 71 figures. 2nd ed. Springer-Verlag, 2004.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Nisan, Noam. Using Hard Problems to Create Pseudorandom Generators. MIT Press, 2003.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Kohli, Pushmeet, Youssef Hamadi, and Lucas Bordeaux. Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 2014.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kohli, Pushmeet, Youssef Hamadi, Lucas Bordeaux, and Robert Mateescu. Tractability: Practical Approaches to Hard Problems. Cambridge University Press, 2014.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

Bos, Joppe, and Martijn Stam, eds. Computational Cryptography. Cambridge University Press, 2021. http://dx.doi.org/10.1017/9781108854207.

Full text

Abstract:

The area of computational cryptography is dedicated to the development of effective methods in algorithmic number theory that improve implementation of cryptosystems or further their cryptanalysis. This book is a tribute to Arjen K. Lenstra, one of the key contributors to the field, on the occasion of his 65th birthday, covering his best-known scientific achievements in the field. Students and security engineers will appreciate this no-nonsense introduction to the hard mathematical problems used in cryptography and on which cybersecurity is built, as well as the overview of recent advances on

APA, Harvard, Vancouver, ISO, and other styles

7

Shaw, Zed. Learn C the Hard Way: Practical Exercises on the Computational Subjects You Keep Avoiding. Addison-Wesley Longman, Incorporated, 2015.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Shaw, Zed. Learn C the Hard Way: Practical Exercises on the Computational Subjects You Keep Avoiding. Addison-Wesley Longman, Incorporated, 2015.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

Dasgupta, Subrata. The Second Age of Computer Science. Oxford University Press, 2018. http://dx.doi.org/10.1093/oso/9780190843861.001.0001.

Full text

Abstract:

By the end of the 1960s, a new discipline named computer science had come into being. A new scientific paradigm--the 'computational paradigm'--was in place, suggesting that computer science had reached a certain level of maturity. Yet as a science it was still precociously young. New forces, some technological, some socio-economic, some cognitive impinged upon it, the outcome of which was that new kinds of computational problems arose over the next two decades. Indeed, by the beginning of the 1990's the structure of the computational paradigm looked markedly different in many important respect

APA, Harvard, Vancouver, ISO, and other styles

10

Trost, Harald. Morphology. Edited by Ruslan Mitkov. Oxford University Press, 2012. http://dx.doi.org/10.1093/oxfordhb/9780199276349.013.0002.

Full text

Abstract:

This article discusses in detail computational morphology with examples from various languages. It deals with the processing of words in both their graphemic, i.e. written, and their phonemic, i.e. spoken form. It has a wide range of practical applications such as spelling correction or automated hyphenation. It further seeks the fact that these tasks may seem simple to a human but they pose hard problems to a computer program. This article provides insights into why this is so and what techniques are available to tackle these tasks. It discusses the sort of information that is expressed by mo

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Computationally hard problems"

1

Akshay, S., Krishnendu Chatterjee, Tobias Meggendorfer, and Đorđe Žikelić. "MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives." In Computer Aided Verification. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-37709-9_5.

Full text

Abstract:

AbstractMarkov decision processes can be viewed as transformers of probability distributions. While this view is useful from a practical standpoint to reason about trajectories of distributions, basic reachability and safety problems are known to be computationally intractable (i.e., Skolem-hard) to solve in such models. Further, we show that even for simple examples of MDPs, strategies for safety objectives over distributions can require infinite memory and randomization.In light of this, we present a novel overapproximation approach to synthesize strategies in an MDP, such that a safety obje

APA, Harvard, Vancouver, ISO, and other styles

2

Meaney, Tamsin, Elena Severina, Monica Gustavsen, Camilla S. Hoven, and Sofie B. Larsen. "Mathematical and Computational Thinking in Children’s Problem Solving with Robots." In Teaching Mathematics as to be Meaningful – Foregrounding Play and Children’s Perspectives. Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-37663-4_8.

Full text

Abstract:

AbstractProgrammable robots are now found in many early childhood centres. However, little research has considered how young children’s problem solving may link computational thinking to mathematical understandings. While most research about robots in kindergarten is from intervention studies to improve children’s computational thinking, in this study we observed two children solving tasks with a robot in a naturalistic setting. We identified when the children had a problem that they could not immediately solve, by looking for signs of uncertainty, for example by putting their hand to their mo

APA, Harvard, Vancouver, ISO, and other styles

3

Ko, Ker-I., Pekka Orponen, Uwe Schöning, and Osamu Watanabe. "What is a hard instance of a computational problem?" In Structure in Complexity Theory. Springer Berlin Heidelberg, 1986. http://dx.doi.org/10.1007/3-540-16486-3_99.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Blin, Guillaume, Guillaume Fertin, Romeo Rizzi, and Stéphane Vialette. "What Makes the Arc-Preserving Subsequence Problem Hard?" In Transactions on Computational Systems Biology II. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11567752_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Frausto-Solís, Juan, and Alma Nieto-Yáñez. "An Improved Simplex-Genetic Method to Solve Hard Linear Programming Problems." In Computational Science – ICCS 2007. Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-72590-9_150.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Ye, Bin, Jun Sun, and Wen-Bo Xu. "Solving the Hard Knapsack Problems with a Binary Particle Swarm Approach." In Computational Intelligence and Bioinformatics. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11816102_17.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Aine, Sandip, Rajeev Kumar, and P. P. Chakrabarti. "An Adaptive Framework for Solving Multiple Hard Problems Under Time Constraints." In Computational Intelligence and Security. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11596448_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Jerome Moses, M., and Ayyagari Ramakalyan. "A Computationally Faster Randomized Algorithm for NP-Hard Controller Design Problem." In Advances in Intelligent Systems and Computing. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-01778-5_42.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Gusfield, Dan, and Hannah Brown. "Unified SAT-Solving for Hard Problems of Phylogenetic Network Construction." In Computational Advances in Bio and Medical Sciences. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-17531-2_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Zheng, Zhiyong, Kun Tian, and Fengxia Liu. "Learning with Error." In Financial Mathematics and Fintech. Springer Nature Singapore, 2022. http://dx.doi.org/10.1007/978-981-19-7644-5_3.

Full text

Abstract:

AbstractLearning with error was proposed by O. Regev in 2005 (see Regev, 2009), which can be regarded as a dual form of SIS problem. LWE has very important applications in modern cryptography, such as LWE-based fully homomorphic encryption. The main purpose of this chapter is to explain the mathematical principles of the LWE problem in detail, especially the polynomial equivalence between the average LWE problem and the hard problems on lattice, which is one generalization of the Ajtai reduction principle and solves the computational complexity of the LWE problem effectively.

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Computationally hard problems"

1

Rusovac, Dominik, Markus Hecher, Martin Gebser, Sarah Alice Gaggl, and Johannes K. Fichte. "Navigating and Querying Answer Sets: How Hard Is It Really and Why?" In 21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/kr.2024/60.

Full text

Abstract:

Answer set programming is a popular declarative paradigm with countless applications for modeling and solving combinatorial problems. We can view a program as a knowledge database compactly representing conditions for solutions. Often we are interested in reasoning about solutions of filtering answer sets. At the heart of these questions is brave and cautious reasoning. For browsing answer sets, we combine both as restricting atoms of answer sets is only meaningful for atoms called facets that belong to some (brave) but not to all answer sets (cautious). Surprisingly, the precise computational

APA, Harvard, Vancouver, ISO, and other styles

2

Witczak, Mateusz, Andrzej Majkowski, and Marcin Kołodziej. "Implementation of EMG Signals for Hand Prosthesis Control." In 2024 25th International Conference on Computational Problems of Electrical Engineering (CPEE). IEEE, 2024. http://dx.doi.org/10.1109/cpee64152.2024.10720407.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Ishtaiwi, Abdelraouf, Ahmed HajYasien, Ruzayn Quaddoura, and Waleed Amer. "Hybrid Metaheuristic Algorithms with Dynamic Clause Weight Adjustments for Efficient Optimization of NP-Hard Problems." In 2025 1st International Conference on Computational Intelligence Approaches and Applications (ICCIAA). IEEE, 2025. https://doi.org/10.1109/icciaa65327.2025.11013656.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Piedra-Jimenez, Frank, Ana In�s Torres, and Maria Analia Rodriguez. "A Comparison of Robust Modeling Approaches to Cope with Uncertainty in Independent Terms, considering the Forest Supply Chain Case Study." In The 35th European Symposium on Computer Aided Process Engineering. PSE Press, 2025. https://doi.org/10.69997/sct.158419.

Full text

Abstract:

Uncertainty plays a crucial role in strategic supply chain design. In this study, we explore robust approaches to model uncertainty when the non-deterministic parameters are placed in the independent term, on the right-hand side (RHS) of the constraints. We consider the "disjunctive adjustable column-wise robust optimization" (DACWRO), a disjunctive formulation introduced previously in our group, and compare it with the adjustable column-wise robust optimization (ACWRO) formulation, a specific technique for solving robust optimization problems when the original robust optimization approach may

APA, Harvard, Vancouver, ISO, and other styles

5

Bashar, Mohammad Khairul, Jaykumar Vaidya, R. S. Surya Kanthi, et al. "Ferroelectric-based Accelerators for Computationally Hard Problems." In GLSVLSI '21: Great Lakes Symposium on VLSI 2021. ACM, 2021. http://dx.doi.org/10.1145/3453688.3461745.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Yang, Yongjie. "How Hard Is It to Impact the Impact of Your Paper?" In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/335.

Full text

Abstract:

Consolidation-disruption index (CD index) is a new metric for qualitatively measuring the contribution of a patent or a research paper. We embark on the study of the complexity of the CD index manipulation problems, which model scenarios where scholars seek to enhance the CD indices of their papers through the merging, addition, or deletion of papers. We show that these problems are generally computationally hard, even when restricted to very realistic special cases. Specifically, we analyze how various parameters influence the parameterized complexity of these problems.

APA, Harvard, Vancouver, ISO, and other styles

7

Schierreich, Šimon. "Multivariate Analysis and Structural Restrictions in Computational Social Choice." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/966.

Full text

Abstract:

In my research, I focus on computationally hard problems in the area of computational social choice. I am interested in the study of input restrictions that guarantee the existence of efficient and scalable algorithms that can be of practical interest.

APA, Harvard, Vancouver, ISO, and other styles

8

de Haan, Ronald, and Marija Slavkovik. "Answer Set Programming for Judgment Aggregation." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/231.

Full text

Abstract:

Judgment aggregation (JA) studies how to aggregate truth valuations on logically related issues. Computing the outcome of aggregation procedures is notoriously computationally hard, which is the likely reason that no implementation of them exists as of yet. However, even hard problems sometimes need to be solved. The worst-case computational complexity of answer set programming (ASP) matches that of most problems in judgment aggregation. We take advantage of this and propose a natural and modular encoding of various judgment aggregation procedures and related problems in JA into ASP. With thes

APA, Harvard, Vancouver, ISO, and other styles

9

Biswas, Arpan, and Christopher Hoyle. "A Literature Review: Solving Constrained Non-Linear Bi-Level Optimization Problems With Classical Methods." In ASME 2019 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2019. http://dx.doi.org/10.1115/detc2019-97192.

Full text

Abstract:

Abstract Bi-level optimization is an emerging scope of research which consists of two optimization problems, where the lower-level optimization problem is nested into the upper-level problem as a constraint. Bi-level programming has gained much attention recently for practical applications. Bi-level Programming Problems (BLPP) can be solved with classical and heuristic optimization methods. However, applying heuristic methods, though easier to formulate for realistic complex design, are likely to be too computationally expensive for solving bi-level problems, especially when the problem has hi

APA, Harvard, Vancouver, ISO, and other styles

10

Santos, Edcarllos, Alfredo Candia-Véjar, Luiz Satoru Ochi, Luidi Simonetti, and Uéverton S. Souza. "New Insights on Prize Collecting Path Problems." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3182.

Full text

Abstract:

Given a graph G and a pair s,t in V(G), where each edge e has a weight t(e) and each vertex v has a value p(v) such that t(e) represent a transportation time and p(v) a prize collecting. Prize Collecting Path (PCP) consists of finding a (s,t)-path that minimizes the total transportation time minus the total prize of nodes in such path. PCP is at core of numerous relevant applications in several fields like telecommunications, transportation and logistics. In this paper, the complexity behavior of the problem is analyzed. For some cases we prove that PCP is NP-complete, these results lead to th

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Computationally hard problems"

1

Gomes, Carla P. Platform for Principled Experimentation of Hard Computational Problems. Defense Technical Information Center, 2000. http://dx.doi.org/10.21236/ada387508.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Sertkaya, Barış. Some Computational Problems Related to Pseudo-intents. Technische Universität Dresden, 2008. http://dx.doi.org/10.25368/2022.169.

Full text

Abstract:

We investigate the computational complexity of several decision, enumeration and counting problems related to pseudo-intents. We show that given a formal context and a set of its pseudo-intents, checking whether this context has an additional pseudo-intent is in conp and it is at least as hard as checking whether a given simple hypergraph is saturated. We also show that recognizing the set of pseudo-intents is also in conp and it is at least as hard as checking whether a given hypergraph is the transversal hypergraph of another given hypergraph. Moreover, we show that if any of these two probl

APA, Harvard, Vancouver, ISO, and other styles

3

Aursjø, Olav, Aksel Hiorth, Alexey Khrulenko, and Oddbjørn Mathias Nødland. Polymer flooding: Simulation Upscaling Workflow. University of Stavanger, 2021. http://dx.doi.org/10.31265/usps.203.

Full text

Abstract:

There are many issues to consider when implementing polymer flooding offshore. On the practical side one must handle large volumes of polymer in a cost-efficient manner, and it is crucial that the injected polymer solutions maintain their desired rheological properties during transit from surface facilities and into the reservoir. On the other hand, to predict polymer flow in the reservoir, one must conduct simulations to find out which of the mechanisms observed at the pore and core scales are important for field behavior. This report focuses on theoretical aspects relevant for upscaling of p

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!