When Input Integers are Given in the Unary Numeral Representation
Many NP-complete problems take integers as part of their input instances. These input integers are generally binarized, that is, provided in the form of the "binary" numeral representation, and the lengths of such binary forms are used as a basis unit to measure the computational complexity of the problems. In sharp contrast, the "unarization" (or the "unary" numeral representation) of numbers has been known to bring a remarkably different effect onto the computational complexity of the problems. When no computational-complexity difference is observed between binarization and unarization of instances, on the contrary, the problems are said to be strong NP-complete. This work attempts to spotlight an issue of how the unarization of instances affects the computational complexity of various combinatorial problems. We present numerous NP-complete (or even NP-hard) problems, which turn out to be easily solvable when input integers are represented in unary. We then discuss the computational complexities of such problems when taking unary-form integer inputs. We hope that a list of such problems signifies the structural differences between strong NP-completeness and non-strong NP-completeness.
Code (0)
등록된 구현이 없습니다.
Tasks
BinarizationSimilar Papers 제목 키워드 기반
Evaluating the relationship between regularity and learnability in recursive numeral systems using Reinforcement Learning
Human recursive numeral systems (i.e., counting systems such as English base-10 numerals), like many other grammatical systems, are highly regular. Following prior work that relates cross-linguistic tendencies to biases …
Reinforcement LearningFactorization Machine with Quadratic-Optimization Annealing for RNA Inverse Folding and Evaluation of Binary-Integer Encoding and Nucleotide Assignment
The RNA inverse folding problem aims to identify nucleotide sequences that preferentially adopt a given target secondary structure. While various heuristic and machine learning-based approaches have been proposed, many r…
The Effect of Scripts and Formats on LLM Numeracy
Large language models (LLMs) have achieved impressive proficiency in basic arithmetic, rivaling human-level performance on standard numerical tasks. However, little attention has been given to how these models perform wh…
Mathematical ReasoningNUMCoT: Numerals and Units of Measurement in Chain-of-Thought Reasoning using Large Language Models
Numeral systems and units of measurement are two conjoined topics in activities of human beings and have mutual effects with the languages expressing them. Currently, the evaluation of Large Language Models (LLMs) often …
MathMathematical ReasoningAsymptotic stabilization under homomorphic encryption: A re-encryption free method
In this paper, we propose methods to encrypted a pre-given dynamic controller with homomorphic encryption, without re-encrypting the control inputs. We first present a preliminary result showing that the coefficients in …
Quantization