We study search problems and reducibilities between them with known or potential relevance to bounded arithmetic theories. Our primary objective is to understand the sets of low complexity consequences of theories Si2 and Ti2 for a small i, ideally in a rather strong sense of characterization; or, at least, in the standard sense of axiomatization. We also strive for maximum combinatorial simplicity of the characterizations and axiomatizations, eventually sufficient to prove conjectured separation results. To this end two techniques (...) based on the Herbrand's theorem are developed. They characterize/axiomatize Σb1-consequences of Σb2-definable search problems, while the method based on the more involved concept of characterization is easier and gives more transparent results. This method yields new proofs of Buss' witnessing theorem and of the relation between PLS and Σb1, and also an axiomatization of Σb1. (shrink)

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version (...) and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective. (shrink)

We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories $T_{2}^{2}$ and $T_{3}^{2}$.

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. We study a new class of NP search problems, those which can be proved total using standard combinatorial reasoning based on approximate counting. Our model for this kind of reasoning is the bounded arithmetic theory [math] of [E. Jeřábek, Approximate counting by hashing in bounded arithmetic, J. Symb. Log. 74(3) (2009) 829–860]. In particular, the Ramsey and weak pigeonhole search problems lie in the new class. We (...) give a purely computational characterization of this class and show that, relative to an oracle, it does not contain the problem CPLS, a strengthening of PLS. As CPLS is provably total in the theory [math], this shows that [math] does not prove every [math] sentence which is provable in bounded arithmetic. This answers the question posed in [S. Buss, L. A. Kołodziejczyk and N. Thapen, Fragments of approximate counting, J. Symb. Log. 79(2) (2014) 496–525] and represents some progress in the program of separating the levels of the bounded arithmetic hierarchy by low-complexity sentences. Our main technical tool is an extension of the “fixing lemma” from [P. Pudlák and N. Thapen, Random resolution refutations, Comput. Complexity, 28(2) (2019) 185–239], a form of switching lemma, which we use to show that a random partial oracle from a certain distribution will, with high probability, determine an entire computation of a [math] oracle machine. The introduction to the paper is intended to make the statements and context of the results accessible to someone unfamiliar with NP search problems or with bounded arithmetic. (shrink)

We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our (...) search problems are “type-2” NP search problems, which take second-order objects as parameters. (shrink)

We consider exponentially large finite relational structures (with the universe {0.1}ⁿ) whose basic relations are computed by polynomial size (nO(1)) circuits. We study behaviour of such structures when pulled back by P/poly maps to a bigger or to a smaller universe. In particular, we prove that: 1. If there exists a P/poly map g: {0.1} → {0.1}m, n < m, iterable for a proof system then a tautology (independent of g) expressing that a particular size n set is dominating in (...) a size 2ⁿ tournament is hard for the proof system. 2. The search problem WPHP, decoding RSA or finding a collision in a hashing function can be reduced to finding a size m homogeneous subgraph in a size 22m graph. Further we reduce the proof complexity of a concrete tautology (expressing a Ramsey property of a graph) in strong systems to the complexity of implicit proofs of implicit formulas in weak proof systems. (shrink)

We give a new characterization of the strict $$\forall {\Sigma^b_j}$$ sentences provable using $${\Sigma^b_k}$$ induction, for 1 ≤ j ≤ k. As a small application we show that, in a certain sense, Buss’s witnessing theorem for strict $${\Sigma^b_k}$$ formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with (...) j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of $$\forall {\Sigma^b_1}$$ sentences. (shrink)

We investigate the possibility to characterize (multi) functions that are Σ b i -definable with small i (i = 1, 2, 3) in fragments of bounded arithmetic T 2 in terms of natural search problems defined over polynomial-time structures. We obtain the following results: (1) A reformulation of known characterizations of (multi)functions that are Σ b 1 - and Σ b 2 -definable in the theories S 1 2 and T 1 2 . (2) New characterizations of (multi)functions (...) that are Σ b 2 - and Σ b 3 -definable in the theory T 2 2 . (3) A new non-conservation result: the theory T 2 2 (α) is not ∀Σ b 1 (α)-conservative over the theory S 2 2 (α). To prove that the theory T 2 2 (α) is not ∀Σ b 1 (α)-conservative over the theory S 2 2 (α), we present two examples of a Σ b 1 (α)-principle separating the two theories: (a) the weak pigeonhole principle WPHP (a 2 , f, g) formalizing that no function f is a bijection between a 2 and a with the inverse g, (b) the iteration principle Iter (a, R, f) formalizing that no function f defined on a strict partial order ( $\{0,\dots,a\}$ , R) can have increasing iterates. (shrink)

There is a long history in science and technology studies of tracking problematic objects, such as controversies, matters of concern, and issues, using various digital tools. But what happens when public problems do not play out in these familiar ways? In this paper, we will think through the methodological implications of studying “problems” in relation to recent events surrounding the sharing of patient data in the National Health Service in the United Kingdom. When a data sharing agreement called (...) care.data was announced in 2013, nearly 1.5 million citizens chose to opt out. Yet, in subsequent years, there has been little evidence of a robust public mobilising around data sharing. We will attempt to track this elusive ‘non problem’ using some digital tools developed in STS for the purpose of mapping issues and problem definitions within science. Although we find these digital tools are unable to capture the “problem,” the process of searching helps us map the terrain of the case and forces us to consider wider definitions. (shrink)

Learning to solve a class of problems can be characterized as a search through a space of hypotheses about the rules for solving these problems. A series of four experiments studied how different learning conditions affected the search among hypotheses about the solution rule for a simple computational problem. Experiment 1 showed that a problem property such as computational difficulty of the rules biased the search process and so affected learning. Experiment 2 examined the impact (...) of examples as instructional tools and found that their effectiveness was determined by whether they uniquely pointed to the correct rule. Experiment 3 compared verbal directions with examples and found that both could guide search. The final experiment tried to improve learning by using more explicit verbal directions or by adding scaffolding to the example. While both manipulations improved learning, learning still took the form of a search through a hypothesis space of possible rules. We describe a model that embodies two assumptions: the instruction can bias the rules participants hypothesize rather than directly be encoded into a rule; participants do not have memory for past wrong hypotheses and are likely to retry them. These assumptions are realized in a Markov model that fits all the data by estimating two sets of probabilities. First, the learning condition induced one set of Start probabilities of trying various rules. Second, should this first hypothesis prove wrong, the learning condition induced a second set of Choice probabilities of considering various rules. These findings broaden our understanding of effective instruction and provide implications for instructional design. (shrink)

In the history of European philosophy and science, René Descartes is considered an author of a methodology of radical doubt, meditation, and the conception that explains the cause of human errors. But the course on internalization, knowledge of one's own Self, methodology of searching foundation of knowledge and conception of perfect reason have been formed already in the times of a Late Antiquity, particular by Augustine in his works “Soliloquies” and “Confession”, Boethius’s “The Consolation of Philosophy” and was continued in (...) the New age by Loyola’s “Spiritual exercises” and Teresa of Avila’s “The Interior Castle”. Therefore, Descartes could be rightfully considered rather the brilliant inheritor of this tradition than pioneer. To this chain of philosophers and theologians who were forerunners of Descartes’s theory of Radical doubt and especially problem of the source of human errors worth to add a new name – Hadewijch, the representative of medieval Dutch vernacular theology and her works “Visions” along with “Letters”. Precisely her point of view on cause of human errors, very close to the explanation have been given by Descartes in his IV Meditation. The aim of the research is to demonstrate common positions of Descartes’s and Hadewijch’s explanation of the nature of the errors. (shrink)

The current empirical research and normative arguments on physician-assisted dying in the Netherlands seem insufficient to provide ethical guidance to general practitioners in the practice of PAD, due to a gap between the evidence and arguments on the one hand and the uncertainties and complexities as found in everyday practice on the other. This paper addresses the problems of current ethical arguments and empirical research and how both seem to be profoundly influenced by the Dutch legislative framework on PAD (...) and a certain view on ethics. Furthermore, the paper elaborates on how other approaches to empirical research in bioethics, such as found in the broad field of narrative research, could supplement the empirical and ethical evaluation of PAD in the Netherlands. This paper also addresses the challenging question of how empirical data—in this case narratives—relate to normativity. The paper is written in the form of a personal narrative of the author, a young Dutch general practitioner and researcher in bioethics. This style is intentionally chosen, to illustrate how work context and professional background influence the observations one makes and the questions one may ask about the topic of PAD. In addition, by using this style, this paper not only gives a different perspective on a much-contested bioethical issue, but also on the challenges faced when a physician–bioethicist has to navigate different disciplinary fields and epistemological paradigms, especially since the ‘empirical turn’ in bioethics. (shrink)

Purpose. The purpose of the article is the analysis of the reasons and grounds of the crisis in the sphere of meaning-making, as well as searching answers to the questions about the meaning of human life in the contemporary world, which are maximally relevant in connection with the escalation of global problems, revealing the points of convergence between various theoretical positions, evaluation of their heuristic potential. Theoretical basis of the research is the historical-philosophical, comparative and system approaches, as well (...) as the analysis of philosophical insights in the field of global studies. Originality. Originality lies in the fact that this article is the first attempt to conduct comprehensive analysis in the problem of the sense of the Existence as it is presented in the first quarter of the 21st century and to relate it with the modern social situation that is characterized by a complex range of interconnected and interdependent anthropological problems of our time. Authors emphasize that the main reason in the crisis of meaning is that a man has lost touch with his roots, which is wildlife. He has created an artificial structure, civilization to satisfy his needs and finds no way to the transcendental, which is the true House of his being. Conclusions. A human must refuse from false self-conceit concerning his potential omniscience and omnipotence, cease dictating his own rules to the Existence, determine the boundaries of his freedom and try to clearly realize his place in the objective structure of being. The global situation can change for the better only if a dramatic change in the area of meaning-making happens. The decisive force, which may encourage nudging to the positive changes, can be either the free will of people who have realized the criticality of the situation or external natural and social circumstances that will make people reorganize radically. The proper prioritizing, a deep awareness of universal goals and solidarity between people could be the value basis that will become the foundation to find the meaning and create a more favorable future. (shrink)

Stephen Turner has explored the ongms of social science in this pioneering study of two nineteenth century themes: the search for laws of human social behavior, and the accumulation and analysis of the facts of such behavior through statistical inquiry. The disputes were vigorously argued; they were over questions of method, criteria of explanation, interpretations of probability, understandings of causation as such and of historical causation in particular, and time and again over the ways of using a natural science (...) model. From his careful elucidation of John Stuart Mill's proposals for the methodology of the social sciences on to his original analysis of the methodological claims and practices of Emile Durkheim and Max Weber, Turner has beautifully traced the conflict between statistical sociology and a science offactual description on the one side, and causal laws and a science of nomological explanation on the other. We see the works of Comte and Quetelet, the critical observations of Herschel, Buckle, Venn and Whewell, and the tough scepticism of Pearson, all of these as essential to the works of the classical founders of sociology. With Durkheim's essay on Suicide and Weber's monograph on The Protestant Ethic, Turner provides both philosophical analysis to demonstrate the continuing puzzles over cause and probability and also a perceptive and wry account of just how the puzzles of our late twentieth century are of a piece with theirs. The terms are still familiar: reasons vs. (shrink)

The purpose of this paper is to show how certain uses of search-engine technology raise concerns for personal privacy. In particular, we examine some privacy implications involving the use of search engines to acquire information about persons. We consider both a hypothetical scenario and an actual case in which one or more search engines are used to find information about an individual. In analyzing these two cases, we note that both illustrate an existing problem that has been (...) exacerbated by the use of search engines and the Internet – viz., the problem of articulating key distinctions involving the public vs. private aspects of personal information. We then draw a distinction between “public personal information” and “nonpublic personal information” to see how this scheme can be applied to a problem of protecting some forms of personal information that are now easily manipulated by computers and search engines – a concern that, following Helen Nissenbaum , we describe as the problem of privacy in public. (shrink)

ISBN 978-5-86007-556-6. (in Russian). -/- In the book we can find the analysis of some closely related problems – of the origin and essence of life, the universal world process and the global evolution. Examination of fractal nature of carriers through the distribution of terrestrial and space objects on the steps of scale staircase, depending on the masses and sizes, shows an appropriate relationship with the masses and sizes of live organisms. One of the conclusions is the complementarity of (...) living and nonliving carriers in universe, and the main difference between a living from nonliving matter is an independent source of ordering inherent in living forms and managing all of its reactions. Tables 9. Fig. 11. Ref. 60 titles. (shrink)

This chapter contains sections titled: Early Existentialism Phenomenology Phenomenological Existentialism French Existentialism The Problem of the Political in Existentialism and Phenomenology.

The central task of cognitive neuroscience to map cognitive capacities to neural mechanisms faces three interlocking conceptual problems that together frame the problem of cognitive ontology. First, they must establish which tasks elicit which cognitive capacities, and specifically when different tasks elicit the same capacity. To address this operationalization problem, scientists often assess whether the tasks engage the same neural mechanisms. But to determine whether mechanisms are of the same or different kinds, we need to solve the abstraction problem (...) by determining which mechanistic differences are and are not relevant, and also the boundary problem by distinguishing the mechanism from its background conditions. Solving these problems, in turn, requires understanding how cognitive capacities are elicited in tasks. These three problems, which have been noted and discussed elsewhere in the literature, together form a ‘cycle of kinds’ that frames the central problem-space of cognitive ontology. We describe this cycle to clarify the intellectual challenges facing the cognitive ontologist and to reveal the kind of iterative process by which ontological revision in cognitive neuroscience is likely to unfold. (shrink)

Timetabling problems are specific types of scheduling problems that deal with assigning certain events to the timeslots. This assigning is subject to certain hard constraints that should be achieved to get a feasible timetable and soft constraints that must meet as many as possible during forming a feasible schedule. This paper introduces an adaptive tabu search. Eleven benchmark datasets of the year 2002 are applied to show the effectiveness of the introduced algorithm. These datasets consist of 5-small, (...) 5-medium, and 1-large dataset. As compared to other methods from previous works, the proposed algorithm produces excellent timetables, in comparison with the algorithms as well as the current results, the mathematical results showed the high effectiveness of the suggested algorithm. It has a minor deficit on the medium or the small problem adaptive Tabu, and the tabu search relies on the tabu list and penalty cost when the change in the penalty cost is checked; if it is still unchanged for the period of iterations (1,000 iterations), the tabu list reduces automatically by (−2); furthermore, the tabu list remains constant. (shrink)

The text was originally a conference speech. In principle, it was prepared for teachers of philosophy and people interested in philosophy, therefore it has the character of an essay and only to a small extent refers to the literature of the subject. However, I am deeply convinced of the validity of the thesis that I propose in it, even if they may seem only to a small extent supported by references to the state of research. -/- Synthetical studies take a (...) special place in the research on the history of ancient philosophy. They demonstrate the existing perspective by performing a selection and arrangement of the material, presenting the periodisation, accentuating and determining what is “philosophically significant.” This article points out that despite the great progress made in detailed research that has taken place over the last few decades, the general framework of development of philosophy, derived from Hegel’s thought, has remained unchanged for two centuries. Hegel’s perspective has instilled a certain pattern that encompasses a whole series of debatable solutions. These include (1) development of a certain understanding of what “philosophy” is and thus separating it from a wide spectrum of literature, rhetoric, medicine, and religion; (2) introduction of a dubious periodisation (e.g. the distinction between the Presocratic period and Socrates’ breakthrough in the form of a departure from the philosophy of nature and return to ethical considerations; (3) adoption of philosophy of Plato and Aristotle as the apex of thought. The author highlights the need to change the approach to the history of ancient philosophy and modify the existing paradigm. He calls for paying greater attention to the intertextual element and to the fact that the assessment of originality and relevance of preserved works is falsified due to the disappearance of comparative material. The proposal to establish a new reconstructive paradigm is based on the belief that during further research on ancient philosophy it would be advisable (1) to expand the research perspective and enrich it with the fields of education, medicine, the great sphere of literature, the spheres of fine arts and music, (2) to focus more on the issue of transmission and reception of texts thanks to which it is possible to deepen and extend the reconstructed context of philosophical discussions, (3) to come to the realisation that the abstract character of description, connected with all the syntheses of the philosophical thought in antiquity lead to its oversimplification and impoverishment by presenting it out of the context and depriving of what is individual and specific for a particular thinker. (shrink)

This paper argues that while the classical, essentialist conception of identity is appealing due to its simplicity, it does not adequately capture the complexity of professional or individual identity. The appeal to essentialism in librarianship contributes to some serious problems for the profession, such as exclusion and homogeneity in the workplace, high attrition rates of minority librarians, exploitation and alienation of an underrepresented workforce, as well as stereotyping. This paper examines the theoretical landscape with regard to the identity question (...) and proposes a more fitting alternative to essentialism, namely the relational conception of identity, and engages in a philosophical argument for the adoption of the relational account as a theoretical grounding for an understanding of the complex, fluid, and emergent nature of librarian identity within our dynamic profession. (shrink)

Cowan's experimental techniques cannot constrain subject's recall of presented information to distinct independent chunks in short-term memory (STM). The encoding of associations in long-term memory contaminates recall of pure STM capacity. Even in task environments where the functional independence of chunks is convincingly demonstrated, individuals can increase the storage of independent chunks with deliberate practice – well above the magical number four.

The scope and length of this anthology make it one of the best recent introductions to Continental thought for the English-speaking reader. Despite the editor's efforts to compass a century and a half of European thought under the somewhat inflated title of a "search for being," each of the fourteen contributors is allowed enough space to show that no single problem or quest concretely typifies European philosophical activity in our time. If one overlooks the dramatic cutting and pasting required (...) by the attempt to give an existential flavor to the thinkers, one finds the merit of the book to be precisely the inclusion of authors whose interests are in important respects quite divergent from those of the existentialists. There are new, long translations from Schelling, Ravaisson, Lachelier, Simmel, Husserl, and Heidegger. There is a selected bibliography.--W. H. C. (shrink)

© British Society of Aesthetics 2017. Published by Oxford University Press on behalf of the British Society of Aesthetics. All rights reserved. For Permissions, please email: [email protected] essays collected in Fictional Characters, Real Problems: The Search for Ethical Content in Literature present unique perspectives on the representation of ethical concerns in literature. Edited by Garry L. Hagberg, these essays address different ways that ethical and aesthetic concerns are interwoven in works of long-form literature such as novels and theatrical (...) works. The majority of these essays also support a related claim: due to their long-form nature, these types of literary works provide a reader with ethical perspectives that are both more holistic and nuanced than is possible in typical philosophical thought experiments. Long-form literature affords the time and space to show us the breadth and depth of both our ethical motivations and their consequences.Hagberg has divided this work into... (shrink)

Humans exhibit the remarkable ability to solve complex, multi-step problems despite their limited capacity for search. We review the standard theory of problem solving, which posits that heuristic guidance makes this possible, but we also note that most studies have emphasized the role of domain-specific heuristics, which are not available for unfamiliar tasks, over more general ones. We describe FPS, a flexible architecture for problem solving that supports a variety of different strategies and heuristics, and we report its (...) use in an experiment that studies the effectiveness of two domain-independent criteria. The results suggest that such heuristics can make problem solving far more tractable, and they are generally consistent with our claim that their use offsets the drawbacks of bounded rationality. (shrink)

Literature is a complex and multifaceted expression of our humanity, one dimension of which is ethical content. This striking collection of new essays pursues a fuller and richer understanding of five of the central aspects of this ethical content. These aspects are: the question of character, its formation, and its role in moral discernment; poetic vision in the context of ethical understanding; literature's distinctive role in self-identity and self-understanding; patterns of moral growth and change that emerge from the philosophical reading (...) of literature; and the historical sources and genealogies of some of our most central contemporary conceptions of the ethical dimension of literature. The volume engages with literary work from Homer to J. M. Coetzee, Shakespeare to David Foster Wallace, and explores the philosophy of Plato, Aristotle, Descartes, Locke, Kant, Hegel, Freud, Heidegger, Wittgenstein, Levinas, and others. This rich collection presents some of the best new thinking about the ethical content that lies within literature, and it shows why our reflective absorption in literature is the humane--and humanizing--experience many of us have long taken it to be. (shrink)

Kant was engaged with the subject of theodicy throughout his career and not merely in his 1791 treatise explicitly devoted to the subject. George Huxford traces Kant’s thought on theodicy throughout his career to show not only the continuity of Kant's consideration but also his philosophical development on the subject.